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

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

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

    Подробнее
    Реклама
    Комментарии 0

    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.