Game theory and poker. Counting the number of possible strategies
According to game theory, a pure strategy involves all the moves of all opponents, and for each combination of such moves uniquely sets our turn. Is it possible to win poker with a full analysis of the game tree and enumeration of all pure strategies? Let's start by at least counting the number of pure strategies for each player.
The general idea is as follows. If we have a constructed game tree, then to count the number of pure strategies in “our” nodes, we add the results by the subtrees Fold, Call, Bet / Raise, and multiply in the opponents nodes. If you need to count the number of strategies for another player, you can use the same tree, only the operation (addition / multiplication) in each node will change.
Of course, if the task is only to count the number of strategies, you can do without directly building a tree (as is done in the above code).
Considered Fixed Limit Texas Hold'em, where rates increase no more than 4 times. We perform calculations only for preflop!
')
Code and results - under the cut.
The code was created as a one-time, therefore not to beat strongly bydlokod. The library was used to work with large integer numbers NTL ( link ).
PLAYER_COUNT is replaced by the number of players, MY_POS to the position of the player whose strategies we consider (0 - the small blind, and then in a circle).
I will not give all the results, because it will take a lot of space. I will give only a part.
As you can see, on the button's 6-max-tables, the number of strategies is described by the order number 1805, and this is just pre-flop!
The general idea is as follows. If we have a constructed game tree, then to count the number of pure strategies in “our” nodes, we add the results by the subtrees Fold, Call, Bet / Raise, and multiply in the opponents nodes. If you need to count the number of strategies for another player, you can use the same tree, only the operation (addition / multiplication) in each node will change.
Of course, if the task is only to count the number of strategies, you can do without directly building a tree (as is done in the above code).
Considered Fixed Limit Texas Hold'em, where rates increase no more than 4 times. We perform calculations only for preflop!
')
Code and results - under the cut.
The code was created as a one-time, therefore not to beat strongly bydlokod. The library was used to work with large integer numbers NTL ( link ).
Code
// , , - . // , , 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 is replaced by the number of players, MY_POS to the position of the player whose strategies we consider (0 - the small blind, and then in a circle).
I will not give all the results, because it will take a lot of space. I will give only a part.
results
2 players:
3 players:
6 players:
- 0 - 8
- 1 - 20
3 players:
- 0 - 60805
- 1 - 211960
- 2 - 492912000
6 players:
- five -
As you can see, on the button's 6-max-tables, the number of strategies is described by the order number 1805, and this is just pre-flop!
Source: https://habr.com/ru/post/320958/
All Articles