Теория игр и покер. Подсчитываем число возможных стратегий

Согласно теории игр, чистая стратегия предусматривает все ходы всех противников и на каждую комбинацию таких ходов однозначно задает наш ход. Можно ли победить покер полным анализом дерева игры и перебором всех чистых стратегий? Давайте для начала хотя бы подсчитаем число чистых стратегий каждого игрока.

Общая идея такова. Если у нас есть построенное дерево игры, то для подсчета числа чистых стратегий в «наших» узлах мы складываем результаты по поддеревьям 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 игрока:

• 0 — 8
• 1 — 20

3 игрока:

• 0 — 60805
• 1 — 211960
• 2 — 492912000

6 игроков:

• 5 — 1802202341363657004926496127785285633916128259502205254985934540949258051429695175597912610919067206057971523839629770278251578593917880610557520010254984692164385929345677352041693514377814372796979199294939808091216163754767601141973675170356903205337127023419966319403897530840734012880595369425376716143929987817036701201375991141754800355989995298029970908025862979842915951385622180789763001222979908445378153715862871526258350169722753708880332432838581089176888929519753954534380517877721633418946425185854653853347694048671688953449774940048189175585674908377247349984627461203711603239666866445526584474710942726444679549871784221574694927855614787184129871823387161447964894283112287094228475097476112515692127992957602664721826601182250673053615881561528466116148831742045858965297773300520982894799976404818954937169742858626162197156248308014402763981537833125084940034140982606776017219391292402680752365656838148686056984996040576459883357748414911981765012628508328314119828963113366802349491414460943217633745867506966544484149751487860865957225071184316602456775846830370493330078009057893273543573900499766002913412127395522705023173727177119886301386931050677418689787140164589766726334156804313073123000268115705348905944517159477856332239088110766753085882902138130763205423542251226547843454554651541325030159548960947799057899367933724783990070814679946452150934444075588299373426754719974211167841648784027178062234675179946247275187402500653896102807844639144796583783186406021069715661872548429603476514533249816773905126342362311446700310219604901172986296818405929582933269800999388163883330172905726537786346865575791858543096298847342036874682744065173570956662778140723552503964327431304411985956160939137242995748979377583771370944997621760000000000000000000000000000000

Как можно увидеть, на 6-max-столах у баттона количество стратегий описывается числом 1805-го порядка, и это только префлоп!