- Core War
- Optima Numbers

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 (29 June 1993) by Nándor Sieben
uses the
*classic*algorithm - optima.pas, DOS binary, Windows binary - Corestep v3 (13 May 1994) by Jay Han
uses a non-simulating algorithm to find
*classic*,*alternative*and find-*x*optima steps - corestep.c, DOS binary, Windows binary - Mopt v1.3 (4 June 1996) by Stefan Strack optimizes multiple step sizes with a max gap size and decreasing gap weights - mopt.c, manual, DOS binary, Windows binary
- Optima (29 September 2018) by John Metcalf
uses the
*classic*algorithm - optima.c, Windows binary - pyoptima (3 December 2021) by John Metcalf uses the bomb-free space algorithm - optima.py
- Finally, there are five demo programs for the algorithms listed above opt_cph.c, opt_mid.c, opt_bfs.c, opt_gcd.c, opt_findx.c

## 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:

Mod | 8000 | 8192 | 55440 |
---|---|---|---|

1 | 3039, 3359 | 3455, 3457 | 16211, 23269 |

2 | 2234, 3094 | 3114, 3462, 3438, 3598 | 16238 |

3 | 14691, 15261, 24357 | ||

4 | 3044, 3364 | 3164, 3428 | 22964 |

5 | 2365, 3315 | 21445, 23435 | |

6 | 16134, 21174 | ||

7 | 16373, 21427 | ||

8 | 2376, 2936 | 2200, 2264, 3576, 3592 | 12104, 24184 |

9 | 12087, 21177 | ||

10 | 2430, 2930, 3510 | 19990, 21050 |

## Further Reading

- Steps." Core Warrior 11 (8 Jan 1996). . "
- Quarterly Challenge." The Core War Newsletter 13 (Fall 1992): 12–13. . "
- The Hint." PUSH OFF 20 (7 Sep 1993). . "
- Stones." My First Corewar Book. Self-published, 1994. . "
- Mathematical Models for Step Sizes. Self-published, 1996. (PS, PDF) .
- Bombing/Scanning Pattern." Intro to Art in '88: Paper — Stone — Scissors Trilogy. KOTH.org, 1994. . "