Choosing a good step size is critical to the success of a warrior, so we need a way of measuring the effectiveness of a step size.”

Morrell, Steven C. Mathematical Models for Step Sizes 10 April 1996.

An optima number is a bombing or scanning step with a pattern calculated to efficiently find opponents. The first method for finding optima numbers was discovered by Nándor Sieben in 1992. Several methods with similar, but not identical, results have since been discovered.

Closest Previous Hit

Nándor's classic optima algorithm scores a step by the sum of gaps between each bombed location and the closest previous hit. The higher the score, the more effective the step:

int optima(int step, int coresize)
{
    int gap, pos = step, score = 0, core[MAXCORESIZE] = {0};
    core[0] = core[coresize] = 1;
    while (pos)
    {
        core[pos] = gap = 1;
        while (!core[pos + gap] && !core[pos - gap])
            gap++;
        score += gap;
        pos = (pos + step) % coresize;
    }
    return score;
}

Distance from Midpoint

Jay Han's alternative algorithm scores a step by the sum of distances from each bombed location to the midpoint between the neighbouring previous hits. The lower the score, the more effective the step:

int optima(int step, int coresize)
{
    int gap_up, gap_down, pos = step, score = 0, core[MAXCORESIZE] = {0};
    core[0] = core[coresize] = 1;
    while (pos)
    {
        core[pos] = gap_up = gap_down = 1;
        while (!core[pos + gap_up])
            gap_up++;
        while (!core[pos - gap_down])
            gap_down++;
        score += abs(gap_up - gap_down);
        pos = (pos + step) % coresize;
    }
    return score / 2;
}

Bomb-Free Space

Mark Durham suggested scoring steps by the sum of the largest bomb-free space after each location is bombed. By noting this space will always contain location 0, we can greatly simplify the calculation. The lower the score, the more effective the step:

int optima(int step, int coresize)
{
    int high, low, pos, score = coresize - 1;
    high = low = pos = step;
    while (pos)
        {
            pos = (pos + step) % coresize;
            if (pos > high) high = pos;
            if (pos < low) low = pos;
            score += coresize - high + low - 1;
        }
    return score;
}

Locally Fibonacci Steps

Andy Pierce recommended using steps with gaps which follow a generalized Fibonacci-like sequence. Similar steps can be found by using the time required to calculate gcd(step,coresize) as the score. The higher the score, the more effective the step:

int optima(int step, int coresize)
{
    return !step ? 0 : 1 + optima( coresize % step, step );
}

Find-X Numbers

A step's find-x score shows how quickly an opponent of size x can be found. A step is more efficient when it has a low find-x for common warrior lengths. One method of finding the score is to count the iterations until the bomb-free space is smaller than x:

int findx(int step, int coresize, int find)
{
    int high, low, pos, score = 0;
    high = low = pos = step;
    while (pos != 0 && coresize - high + low > find)
        {
            pos = (pos + step) % coresize;
            if (pos > high) high = pos;
            if (pos < low) low = pos;
            score++;
        }
    return score;
}

Software

Optima Numbers

The bomb-free space optima numbers are listed below for the most common coresizes, with the closest previous hit numbers in italic where they differ:

Mod8000 819255440
13039, 33593455, 345716211, 23269
22234, 3094      3114, 3462, 3438, 359816238
3      14691, 15261, 24357
43044, 33643164, 342822964
52365, 331521445, 23435
616134, 21174
716373, 21427
82376, 29362200, 2264, 3576, 359212104, 24184
912087, 21177
10      2430, 2930, 351019990, 21050

Further Reading

  1. Doligez, Damien. "Steps." Core Warrior 11 (8 Jan 1996).
  2. Durham, Mark A. "Quarterly Challenge." The Core War Newsletter 13 (Fall 1992): 12–13.
  3. Kline, Paul. "The Hint." PUSH OFF 20 (7 Sep 1993).
  4. Morrell, Steven. "Stones." My First Corewar Book. Self-published, 1994.
  5. Morrell, Steven. Mathematical Models for Step Sizes. Self-published, 1996. (PS, PDF)
  6. Wangsaw, Mintardjo. "Bombing/Scanning Pattern." Intro to Art in '88: Paper — Stone — Scissors Trilogy. KOTH.org, 1994.