Poker-AI.org
http://poker-ai.org/phpbb/

#Nodes in a game tree dep. on players and bets (Induction)
http://poker-ai.org/phpbb/viewtopic.php?f=24&t=2717		 Page 1 of 1
Author:  manuel [ Sun Mar 16, 2014 1:33 pm ]
Post subject:  #Nodes in a game tree dep. on players and bets (Induction)
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.
Author:  Pitt [ Mon Mar 17, 2014 11:54 am ]
Post subject:  Re: #Nodes in a game tree dep. on players and bets (Inductio
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.
Author:  manuel [ Tue Mar 18, 2014 10:34 am ]
Post subject:  Re: #Nodes in a game tree dep. on players and bets (Inductio
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:
Author:  Coffee4tw [ Tue Apr 22, 2014 1:43 am ]
Post subject:  Re: #Nodes in a game tree dep. on players and bets (Inductio
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.
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/