Poker-AI.org

Poker AI and Botting Discussion Forum
It is currently Mon Nov 13, 2023 2:10 pm

All times are UTC




Post new topic Reply to topic  [ 4 posts ] 
Author Message
PostPosted: Sun Mar 16, 2014 1:33 pm 
Offline
New Member

Joined: Sun Mar 16, 2014 12:53 pm
Posts: 4
I want to analyze the poker game tree in a mathematical point of view. As always in mathematics one tries to start with a subproblem. Intuitively a tree without a limit on maximal sequential bets is theoretically infinitely large. So there has to be this limit from beginning. For now this recursion is regarding just one betting round. For comprehensibility assume its the river (Game is over at leafnodes). My first approach is the following recursion:

Code:
T(#Players p, #Bet limit b)
T_helper(#Players p, #Bet limit b, #Left actors l)
Initially T(p, b) := T_helper(p, b, p)
Recursive definition:
 
                       T_helper(p, b ,l)
                      /        |        \             
                    /          |          \       
        aggressive/     passive|        fold\ 
                /              |              \     
              /                |                \       
T_helper(p, b-1 , p-1)  T_helper(p, b, l-1)  T_helper(p-1, b, l-1)

T(x,x,0) = 1 (End, all players acted)
T(1,x,x) = 1 (End, all (but one) players folded)
T(x,0,i) = 2^(i+1)-1 (No more raises allowed -> no growth through raises -> Binary tree of depth i)


I tested this recursion and at least for the small values it seems to be correct. Now I want to show the size of the tree by induction. There are two challenging parts.

First is the aggressive branch which resets the left actors to p-1, meaning that the depth of the subtree in this branch gets at least p-1 larger every time a bet is placed. This is the reason why an unlimited amount of bets make the tree grow infinitely. Out of this one can imply that the largest path in this game tree is bounded by the path in which the limit on bets is exhausted and the maximum passive actions is made between the aggressive actions. Hence it follows the maximum path consists of p-1 passive actions (checks) and b times a raise following p-2 (p-1 would finish the round) passive actions (calls), additionally one last call concludes the path.
Code:
maxDepth of T(p, b)
= p-1 + b (1+ p-2) + 1
= p-1 + b(p-1) + 1
= (b+1)(p-1) + 1

Further the smallest path is the length of passive plays in a row, hence minDepth of T(p, b) = p

The second problem I don't know to handle is, that there is some kind of anomaly in the beginning. Initially p is equal to l. Which is, as soon as a bet has been placed, no more possible. This means that the sub trees are not "congruent" to the parent tree.

The following c code can be used to recursively calculate the amount of nodes.

Code:
#include "stdlib.h"
#include "stdio.h"

void T_helper(int p, int b, int l, int* size, int* cont, int* term) {
  if (p == 1){
    ++*size;
    ++*term;
    return;
  }

  if (l == 0){
    ++*size;
    ++*cont;
    return;
  }

  if (b == 0){
    ++*size;
    T_helper(p, b, l-1, size, cont, term);
    T_helper(p-1, b, l-1, size, cont, term);
    return;
  }

  ++*size;
  T_helper(p, b-1, p-1, size, cont, term);
  T_helper(p, b, l-1, size, cont, term);
  T_helper(p-1, b, l-1, size, cont, term);
}

void T(int p, int b, int* size, int* cont, int* term) {
  T_helper(p, b, p, size, cont, term);
}

int main(int argc, char *argv[])
{
  if (argc != 3)
    return 1;

  int size, cont, term;
  T(::atoi(argv[1]), ::atoi(argv[2]), &size, &cont, &term);

  printf("T(%s, %s):\nSize: %d\nContinuing: %d\nTerminating: %d\n",
      argv[1], argv[2], size, cont, term);
  return 0;
}



I unfortunately have never done a proof by induction over several variables. I do not even have a guess on what to proof. So I would appreciate any help.


Top
 Profile  
 
PostPosted: Mon Mar 17, 2014 11:54 am 
Offline
Junior Member

Joined: Wed Dec 04, 2013 12:40 am
Posts: 49
First we don't know what bet limit you're studying. (limit/pot limit/no limit)
It matters because for example in no-limit, when the player with the larger stack pushes on it first move, b goes from it's current value directly to 0, and your recursion doesn't fit.
There's no infinite tree because players have a finite number of chips indeed, but your bet sequence limit size may not be properly propagated during recursion.


What do you want to prove ? I think it's the game tree size but if you have no assertion, you can't prove this assertion :P

########

Induction is simple :

Let's say we keep your betting model and we guess the remaining actions count at any time of play is a function F(p, b, l) that you think is the good one (your assertion, find it first :P ).
Let's call Hp,b,l the hypothesis : "F(p, b, l) returns the remaining subtree size for state described by variables p, b and l" (implicitely, you have to show that p, b and l strictly describe the game state).

Initialization : simply show (or state if it's obvious) H1,b,l for each b and l, and Hp,b,0 for each p and b. Also show that every call leads to those final states (no cycle or divergence).

Recursion : When l > 0 and p > 1 you have 5 possible recursive calls in your function. You have to show that :

* For b > 0, if we suppose Hp,(b-1),(p-1), Hp,b,(l-1) and H(p-1),b,(l-1) then Hp,b,l
* For b = 0, if we suppose Hp,0,(l-1) and H(p-1),0,(l-1) then Hp,b,l

This way you can show that your F function is the good one for each p, b, l

##########

If you want to use your recursive algorithm to find a game tree size formula, you'll have to guess what it could be by looking at simple values, trying to express relations... Find recursive sub-formulas... Hope you enjoy coffee :D

Hope I helped and didn't write too many mistakes.


Top
 Profile  
 
PostPosted: Tue Mar 18, 2014 10:34 am 
Offline
New Member

Joined: Sun Mar 16, 2014 12:53 pm
Posts: 4
Pitt wrote:
First we don't know what bet limit you're studying. (limit/pot limit/no limit)
It matters because for example in no-limit, when the player with the larger stack pushes on it first move, b goes from it's current value directly to 0, and your recursion doesn't fit.
There's no infinite tree because players have a finite number of chips indeed, but your bet sequence limit size may not be properly propagated during recursion.

True. I try to get a explicit (not recursive) and general (for all game types, all players) notation to calculate the upper bound on the game tree's size. E.g. with FL it its b=4; for NL it is theoretically infinte, but you can assume that after 7 minbets (2^7=128) a full stack of 100BB is exceeded, because a minbet has to be at least double the size of the last agressor's bet; I did not take PL into account, but somehow it will fit too, I guess.
I did not consider AllIns. Thats of cause a problem. Then I have to take balance into account, which would make the tree explode. Do you have a solution to this?

Pitt wrote:
What do you want to prove ? I think it's the game tree size but if you have no assertion, you can't prove this assertion :P

Yes, as I said: I do not even have a guess on what to proof. :mrgreen:


Top
 Profile  
 
PostPosted: Tue Apr 22, 2014 1:43 am 
Offline
Site Admin
User avatar

Joined: Thu Feb 28, 2013 5:24 pm
Posts: 230
I don't think you have the longest chain correct. The longest chain will be this:
All players left to act perform passive actions, last player to act min raises, which resets the number of players to act, as you said to p-1.

So for 4 players it will be:
3x call, raise, 2x call, raise, 2x call, ..., raise, 2x call, call (until you run out of raises or money).

Which means for n players with unlimited stack sizes but a bounded raise limit l it's:
n-1 + l * (n-1) + 1 = (l+1)*(n-1) + 1

So for 3 players and raise limit 4 you should have:
5*2+1 = 11

Disclaimer: I did this really quick in my head, could be wrong.

Also, a minbet just needs to raise at least the amount of the last bet, not double the entire bet. Which means you can have a raise sequence of:
2bb, 3bb, 4bb, 5bb, ... (that's the total amount of money put in the pot as a bet, note that the amount raised BY is always 1bb). This is also known as "re-clicking" in online poker terms.

_________________
Cheers.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group