Согласно теории игр, чистая стратегия предусматривает все ходы всех противников и на каждую комбинацию таких ходов однозначно задает наш ход. Можно ли победить покер полным анализом дерева игры и перебором всех чистых стратегий? Давайте для начала хотя бы подсчитаем число чистых стратегий каждого игрока.
Общая идея такова. Если у нас есть построенное дерево игры, то для подсчета числа чистых стратегий в «наших» узлах мы складываем результаты по поддеревьям Fold, Call, Bet/Raise, а в узлах противников умножаем. Если нужно подсчитать число стратегий для другого игрока, можно использовать то же самое дерево, изменится только операция (сложение/умножение) в каждом узле.
Конечно, если задача — только посчитать число стратегий, можно обойтись и без прямого построения дерева (как это и сделано в приведенном коде).
Рассматривается Fixed Limit Texas Hold'em, где ставки повышаются не более 4 раз. Вычисления ведем только для префлопа!
Код и результаты — под катом.
Код создавался как одноразовый, поэтому за быдлокод сильно не бить. Использовалась библиотека для работы с большими целыми числами NTL (ссылка).
// Если сейчас ход оппонента, то беру произведение, если мой ход - сумму.
// Однако если мой ход и я делаю фолд, дальнейшую цепочку не рассматриваем, возврат 1.
#define PLAYER_COUNT 6
#define BB_POS (PLAYER_COUNT-1)
#define MY_POS 5
typedef unsigned char BYTE;
#include <iostream>
#define NTL_NO_MIN_MAX
#include <NTL\ZZ.h>
using namespace std;
using namespace NTL_NAMESPACE;
typedef ZZ longint;
struct PlayerInfo
{
bool active;
BYTE raise_level;
};
struct GameState
{
BYTE last_raise_level;
BYTE active_player_count;
PlayerInfo players [PLAYER_COUNT];
};
BYTE next (BYTE n);
longint turn (GameState &game, int &seq_num, BYTE prev_player, BYTE offset);
void copy_game (GameState &oldg, GameState &newg);
bool is_game_end (GameState &game, BYTE last_player);
void main ()
{
GameState game;
for (BYTE i = 0; i < PLAYER_COUNT; ++i)
{
game.players[i].active = true;
game.players[i].raise_level = 0;
};
game.players[BB_POS].raise_level = 1;
game.last_raise_level = 1;
game.active_player_count = PLAYER_COUNT;
int seq_num = 0;
cout << turn (game, seq_num, BB_POS, 0) << endl;
};
BYTE next(BYTE n)
{
return (n+1) % PLAYER_COUNT;
};
void copy_game (GameState &oldg, GameState &newg)
{
memcpy (&newg, &oldg, sizeof (GameState));
};
bool is_game_end (GameState &game, BYTE last_player)
{
if (game.active_player_count == 1)
return true;
for (BYTE i = 0; i < PLAYER_COUNT; ++i)
if (game.players[i].active && game.players[i].raise_level != game.last_raise_level)
return false;
if (game.last_raise_level == 1)
return last_player == BB_POS;
return true;
};
longint turn (GameState &game, int &seq_num, BYTE prev_player, BYTE offset)
{
if (is_game_end (game, prev_player))
return ZZ(1);
BYTE position = next(prev_player);
if (game.players[position].active)
{
longint result_F;
longint result_C;
longint result_R;
// FOLD
GameState new_game;
copy_game (game, new_game);
new_game.players[position].active = false;
--new_game.active_player_count;
if (position == MY_POS || is_game_end (new_game, position))
result_F = 1;
else
result_F = turn (new_game, seq_num, position, offset+1);
// CALL
copy_game (game, new_game);
new_game.players[position].raise_level = new_game.last_raise_level;
if (is_game_end (new_game, position))
result_C = 1;
else
result_C = turn (new_game, seq_num, position, offset+1);
// RAISE
bool raise_possible = (game.last_raise_level < 4);
if (raise_possible)
{
copy_game (game, new_game);
new_game.last_raise_level = new_game.last_raise_level + 1;
new_game.players[position].raise_level = new_game.last_raise_level;
result_R = turn (new_game, seq_num, position, offset+1);
}
else
result_R = 0;
longint retval;
if (position == MY_POS)
retval = result_F + result_C + result_R;
else if (raise_possible)
retval = result_F * result_C * result_R;
else
retval = result_F * result_C;
return retval;
}
else
return turn (game, seq_num, position, offset);
};
К сожалению, не доступен сервер mySQL