Building a Poker Bot: Functional Fold as Decision Tree Pattern
This is the fifth part of Building a Poker Bot series where I describe my experience developing bot software to play in online poker rooms. I’m building the bot with .NET framework and F# language which makes the task relatively easy and very enjoyable. Here are the previous parts:
- Building a Poker Bot: Card Recognition
- Building a Poker Bot: String and Number Recognition
- Building a Poker Bot: Mouse Movements
- Building a Poker Bot with Akka.NET Actors
In this post I describe a simple pattern to structure the complex decision making code using partial function application and fold operation applied to a list of functions.
Poker decisions are complex and depend on the multitude of parameters and attributes. We can visualize the decision making process as a Decision Tree where leaf nodes are decisions being made, and the branches are different conditions. Here is a simplistic example of such a poker decision tree:
Now, if we need to implement a similar tree in code, the most straightforward way to
do that is to translate each condition to an
if statement. This way, the nested
conditions will guide the application through the branches right to the point where
an appropriate decision can be returned.
This approach works for small cases, but in reality it does not scale particularly well in terms of the tree size. Namely, the two problems are:
Tree depth. In many cases, you might need to pass ten or more conditions before
you find your way to the leaf. Obviously, ten levels of
if statements are not
particularly readable and maintainable. We can try to split the sub-trees into
sub-functions, but that only gives a limited relief.
Subtree correlation. Some tree branches deep down the hiereachy might be correlated to each other. Say, you pass 10 levels of conditions and make a bet on flop. Now, on turn, you would probably take quite a different decision path, but the logic would be based on similar ‘thinking’ in human terms. Ideally, we want to keep this kind of related decisions together, while isolating them from the other unrelated decision paths.
In fact, the decision tree should be generalized to the Decision Graph to allow different decision branches to merge back at some point, e.g.
If there is one Ace on flop, or an overcard came on turn or river
and stacks pre-flop were 20+ BB, or 12+ BB in limped pot
then bet 75% of the pot
There are multiple paths to the same decisions.
Break the decision graph down vertically into smaller chunks. Each chunk should represent multiple layers of conditions and lead to eventual decisions. All conditions in sub-graph should be related to each other (high cohesion) and as isolated from other sub-graphs as possible (low coupling).
Here are two examples of such sub-graphs:
Each sub-graph is very focused on very specific paths and ignores all the branches which do not belong to this decision process. The idea is that those branches will be handled by other sub-graphs.
Represent each sub-graph as a function with arbitrary signature which accepts all the parameters that are required for this sub-graph. Do not accept any parameters which are not related.
The last parameter of each function should be a Maybe of Decision, so should be the function’s return type.
Produce a flat list of all the sub-graph functions. Partially apply the parameters to those functions to unify the signature of all of them.
Now, when making a decision, left-fold the list of functions with the data of
current poker hand. If a function returns
Some value of decision, return it
as the decision produced from the graph.
We define a number of functions, each one of which represents one piece of decision logic. Then we put them all into the list:
let rules = [ overtakeLimpedPot overtakyHand snapshot value history; increaseTurnBetEQvsAI snapshot; allInTurnAfterCheckRaiseInLimpedPot snapshot history; checkCallPairedTurnAfterCallWithSecondPairOnFlop snapshot value.Made history; bluffyCheckRaiseFlopInLimpedPotFlop bluffyCheckRaiseFlopsLimp snapshot value history; bluffyOvertakingRiver bluffyOvertaking snapshot history ]
The type of this list is
(Decision option -> Decision option) list.
Note how each individual function accepts different set of parameters. Current hand’s
snapshot is used by all of them, while calculated hand
value and previous
history are used only by some of the functions.
Now, here is the definition of the facade decision making function:
rules |> List.fold (fun opt rule -> rule opt) None
It calculates the decision by folding the list of rules and passing current decision
None is the initial seed of the fold.
Vertical slices are an efficient way to break down the complex decision making
into smaller cohesive manageable parts. Once you get the parts right, it’s easy
to compose them by folding a flat list of partially applied functions into a
Maybe of decision result.