- 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
number of division steps required to calculate gcd(step,coresize)
as the score, which is equivalent to the number of terms in the continued
fraction for coresize / step. 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 finder #1 (6 December 2002) by M Joonas Pihlaja is an optima number finder written in Redcode - optima1.red
- Optima (29 September 2018) uses the classic algorithm - optima.c, Windows binary
- pyoptima (3 December 2021) is a Python implementation of the bomb-free space algorithm - optima.py
- rubyoptima (15 July 2023) is a Ruby implementation of the bomb-free space algorithm - optima.rb v0.3, v0.2, v0.1
- roptima (9 February 2025) is a R implementation of the bomb-free space algorithm - optima.r
- jloptima (28 September 2025) is a Julia implementation of the bomb-free space algorithm - optima.jl
- optima_cf (8 August 2026) is a Ruby implementation of the continued fraction algorithm - optima_cf.rb
- 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.