Согласно теории игр, чистая стратегия предусматривает все ходы всех противников и на каждую комбинацию таких ходов однозначно задает наш ход. Можно ли победить покер полным анализом дерева игры и перебором всех чистых стратегий? Давайте для начала хотя бы подсчитаем число чистых стратегий каждого игрока.
Общая идея такова. Если у нас есть построенное дерево игры, то для подсчета числа чистых стратегий в «наших» узлах мы складываем результаты по поддеревьям Fold, Call, Bet/Raise, а в узлах противников умножаем. Если нужно подсчитать число стратегий для другого игрока, можно использовать то же самое дерево, изменится только операция (сложение/умножение) в каждом узле.
Конечно, если задача — только посчитать число стратегий, можно обойтись и без прямого построения дерева (как это и сделано в приведенном коде).
Рассматривается Fixed Limit Texas Hold'em, где ставки повышаются не более 4 раз. Вычисления ведем только для префлопа!
Код и результаты — под катом.
Код создавался как одноразовый, поэтому за быдлокод сильно не бить. Использовалась библиотека для работы с большими целыми числами NTL (ссылка).
PLAYER_COUNT заменить на число игроков, MY_POS на позицию игрока, чьи стратегии считаем (0 — малый блайнд, и далее по кругу).
Не буду приводить все результаты, поскольку это займет много места. Приведу лишь часть.
Как можно увидеть, на 6-max-столах у баттона количество стратегий описывается числом 1805-го порядка, и это только префлоп!
Общая идея такова. Если у нас есть построенное дерево игры, то для подсчета числа чистых стратегий в «наших» узлах мы складываем результаты по поддеревьям 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);
};
PLAYER_COUNT заменить на число игроков, MY_POS на позицию игрока, чьи стратегии считаем (0 — малый блайнд, и далее по кругу).
Не буду приводить все результаты, поскольку это займет много места. Приведу лишь часть.
Результаты
2 игрока:
3 игрока:
6 игроков:
- 0 — 8
- 1 — 20
3 игрока:
- 0 — 60805
- 1 — 211960
- 2 — 492912000
6 игроков:
- 5 — 1802202341363657004926496127785285633916128259502205254985934540949258051429695175597912610919067206057971523839629770278251578593917880610557520010254984692164385929345677352041693514377814372796979199294939808091216163754767601141973675170356903205337127023419966319403897530840734012880595369425376716143929987817036701201375991141754800355989995298029970908025862979842915951385622180789763001222979908445378153715862871526258350169722753708880332432838581089176888929519753954534380517877721633418946425185854653853347694048671688953449774940048189175585674908377247349984627461203711603239666866445526584474710942726444679549871784221574694927855614787184129871823387161447964894283112287094228475097476112515692127992957602664721826601182250673053615881561528466116148831742045858965297773300520982894799976404818954937169742858626162197156248308014402763981537833125084940034140982606776017219391292402680752365656838148686056984996040576459883357748414911981765012628508328314119828963113366802349491414460943217633745867506966544484149751487860865957225071184316602456775846830370493330078009057893273543573900499766002913412127395522705023173727177119886301386931050677418689787140164589766726334156804313073123000268115705348905944517159477856332239088110766753085882902138130763205423542251226547843454554651541325030159548960947799057899367933724783990070814679946452150934444075588299373426754719974211167841648784027178062234675179946247275187402500653896102807844639144796583783186406021069715661872548429603476514533249816773905126342362311446700310219604901172986296818405929582933269800999388163883330172905726537786346865575791858543096298847342036874682744065173570956662778140723552503964327431304411985956160939137242995748979377583771370944997621760000000000000000000000000000000
Как можно увидеть, на 6-max-столах у баттона количество стратегий описывается числом 1805-го порядка, и это только префлоп!
Поделиться с друзьями