Я нашел оптимальную стратегию в этой статье: http://www.rand.org/pubs/research_memoranda/2006/RM408.pdf
Давайте назовем эту стратегию Блотто.
Посмотрите на диаграмму выше.Любое ваше движение может быть представлено точкой на треугольнике.Стратегия в документе гласит, что нужно выбрать произвольную точку в шестиугольнике.Выберите точки ближе к краю шестиугольника с большей вероятностью (0 вероятностей для центра шестиугольника и линейно масштабируйте до максимальной вероятности на контуре шестиугольника. Каждая точка на контуре шестиугольника имеет равную вероятность.)
Это решение для «непрерывного» блотто, но я предполагаю, что вас интересует дискретный случай (разделение N войск на 3 группы).Применение стратегии Блотто к дискретному случаю работает отлично, когда N кратно 3. Для других значений N я смог сделать небольшую корректировку на границе шестиугольника, которая работает очень хорошо, но не идеально.
Если есть стратегия, которая может победить эту, должен быть какой-то статический ход, который выигрывает у стратегии Блотто.Их нет, за исключением случаев, когда N не кратно 3, поэтому кажется, что ход на линии, где встречаются большой треугольник и шестиугольник (например, ход <0, .5, .5>), выиграет у стратегии Блотто немного больше, чем проиграть.Для N = 100 разница, по-видимому, составляет менее 1% и продолжает уменьшаться для больших N.
Код для реализации стратегии Блотто:
// generate a random number in the range [0,x) -- compensate for rand()%x being slightly un-uniform
int rnd( int x ) { int r; while ( 1 ) { r = rand(); if ( r < RAND_MAX/x*x ) return r % x; } }
// distance from center of triangle/hexagon to (x,y,z), multiplied by 3 (trilinear coordinates)
int hexagonalDist3( int x, int y, int z, int N ) { return max(max(abs(N-x*3),abs(N-y*3)),abs(N-z*3)); }
void generateRandomSimpleBlottoMove( int& x, int& y, int& z, int totalTroops )
{
int N = totalTroops;
while ( true )
{
x = rnd(N+1);
y = rnd(N+1);
z = N-x-y;
// keep only moves in hexagon, with moves closer to the border having higher probability
double relativeProbabilityOfKeepingThisMove = hexagonalDist3(x,y,z,N) > N ? 0 : hexagonalDist3(x,y,z,N);
// minor adjustment for hexagon border when N is not a multiple of 3 -- not perfect, but "very close"
if ( N % 3 != 0 && hexagonalDist3(x,y,z,N) == N )
relativeProbabilityOfKeepingThisMove = N*(N%3)/3;
// possibly keep our move
if ( rnd(N) < relativeProbabilityOfKeepingThisMove )
break;
}
}