Posted Wed Dec 07, 2005 6:40 am GMT by Muck
I was asked about how I implemented some of the business logic from my poker game. I decide to post it here and link to it because this sub forum is more appropriate.
Did you know that participating in a poker forum can help you improve your own game? Be it by sharing experiences or simply asking for help, participation in a forum helps you focus and keep 'on topic' which will help you improve your game. You can learn from other players feedback and from their experiences. Why the THP poker forums? We offer one of the best managed texas holdem poker forums available, and the community within is far more friendly than those typicaly found on other sites. We've made a 'lurkers edition' of the poker forum available here on Holdem Poker Online, but we encourage all visitors to register and join in on the conversations on TexasHoldem-Poker.com
Posted Wed Dec 07, 2005 6:44 am GMT by wEbMaStEr
Ohhh. This will be interesting, just let me fetch my reading glasses ......
Posted Wed Dec 07, 2005 6:47 am GMT by Muck
4.2.3 Showdowns
At the end of each hand the money in the pot is given to the winner or distributed among the multiple winners.
To decide who gets the pot each active player must state what his or her highest possible hand is.
The five-card hand each player puts forward as their best must be created from the seven cards available to them (their two private cards plus the five community cards on the board).
Working out a player’s best hand can be the most confusing aspect of poker variants that involve community cards. Fortunately for new players, this responsibility is handled by the game engine, allowing them to win without having to know all of the hand ranks.
The diagram below (see fig 4.2.3.1 “Card selection”) shows a simplified explanation of how a hand is chosen from the cards available. In this example the highest card wins. If the highest cards match (which can happen since five of the available cards can be shared) then the seconds highest is compared and so on down to the last card.
fig 4.2.3.1 “Card selection”
As we can see in the example above (see fig 4.2.3.1 “Card Selection”) the first four cards of each player’s hand have equal value. But player 2 has an 8 as their final card where as player 1 only has a 5. So player 2 wins with the best hand.
Two algorithms implemented the process of finding each player’s highest hand. The first generates the hands and the second ranks them so that they can be compared.
4.2.3.1 Hand Generation
Every possible hand combination is generated and compared. The highest one found is then returned. There were two possible ways this could have been done and I decide to choose efficiency over simplicity.
The first solution was to use a series of nested loops that would increment through each of the seven available cards to fill one of the five available spaces. This would have been simplest to code but was highly inefficient since it didn’t allow for repetition and in poker the order of the cards doesn’t matter (a hand can be though of as a set of cards).
The algorithms complexity can be seen in the equation below.
C The number of different cards available to fill a space in the hand.
H The number of spaces available in the hand to be filled.
T The number of times the comparison method needs to be called.
_H
C = T
So with seven cards available and five spaces to fill we get:
_5
7 = 16807
The second solution was to predefine the entire set of card combinations, minus the repeated ones and store them in an array. This can be seen in the code below:
| Code: |
// BoardHands.java --------------------------------------------------
//A 2D array of all possible card combinations.
int [][] POSSIBLE_HAND_COMBINATIONS =
{{0,1,2,3,4},{0,1,2,3,5},{0,1,2,3,6},{0,1,2,4,5},{0,1,2,4,6},
{0,1,2,5,6},{0,1,3,4,5},{0,1,3,4,6},{0,1,3,5,6},{0,1,4,5,6},
{0,2,3,4,5},{0,2,3,4,6},{0,2,3,5,6},{0,2,4,5,6},{0,3,4,5,6},
{1,2,3,4,5},{1,2,3,4,6},{1,2,3,5,6},{1,2,4,5,6},{1,3,4,5,6}, {2,3,4,5,6}};
avalibleCards[2] = boardCards[0];
avalibleCards[3] = boardCards[1];
avalibleCards[4] = boardCards[2];
avalibleCards[5] = boardCards[3];
avalibleCards[6] = boardCards[4];
avalibleCards[0] = player.getHoleCardAt(0);
avalibleCards[1] = player.getHoleCardAt(1);
//Check every possible hand combination.
for (int intCol = 0; intCol < 21; intCol++)
{
currentHand = new Hand(
avalibleCards[POSSIBLE_HAND_COMBINATIONS[intCol][0]],
avalibleCards[POSSIBLE_HAND_COMBINATIONS[intCol][1]],
avalibleCards[POSSIBLE_HAND_COMBINATIONS[intCol][2]],
avalibleCards[POSSIBLE_HAND_COMBINATIONS[intCol][3]],
avalibleCards[POSSIBLE_HAND_COMBINATIONS[intCol][4]]);
if (intCol == 0)
{
bestHandSoFar = currentHand;
}
//If the new hand is better than the current best one stored
//change the one stored to the new one.
if (bestHandSoFar.lessThan(currentHand))
{
bestHandSoFar = currentHand;
}
}
//-------------------------------------------------------------------
|
This solution only requires 21 hand comparisons.
4.2.3.2 Hand comparisons
Understanding the rank of a poker hand falls within the scope of the hand class. It can compare hands and decide if one is less than the other. To do this it first converts them in to a numerical format.
The diagram below (see fig 4.2.3.2.1 “Hand comparison”) shows how a hands value is stored using an array.
fig 4.2.3.2.1 “Hand comparison”
The first array index stores the most significant number. This represents one of the nine named hand ranks of poker. The values that follow are used in the event of a tie and decrease in significance as they go down.
These values are then compared using the code below:
| Code: |
// Hand.java --------------------------------------------------------
public boolean lessThan(Hand secondHand)
{
...
//If hands are equal return false.
boolean bolLessThan = false;
for (int intIndex = 0; intIndex < handValue.length; intIndex++)
{
if(handValue[intIndex] != secondHandValue[intIndex])
{
if(handValue[intIndex] < secondHandValue[intIndex])
{
bolLessThan = true;
}
else
{
bolLessThan = false;
}
//Exit loop.
intIndex = handValue.length;
}
}
return bolLessThan;
}
//-------------------------------------------------------------------
|
The alternative method would have been to store the hands value in a single integer. The values below are equivalent to the examples above (see fig 4.2.3.2.1 “Hand comparison”).
| Code: |
Highest card = 011311090403
Two pair = 031209100000
Straight = 050900000000
|
This would have made comparisons much quicker, but the value would have been harder to create, manipulate in other methods and read when debugging. So for these reasons I choose the more flexible solution over the more efficient one.
Posted Wed Dec 07, 2005 6:49 am GMT by Muck
4.2.4 Side pots and Split pots
I originally intended to store the pot (see appendices) as a single integer value. But during the design phase of the betting system I discover the pot was a far more complicated data structure, because I hadn’t allowed for the possibility of side pots.
The scenario below explains why side pots are created and how they are shared out at the end.
Mike, Alex, Jon and Dave all bet £200 into the pot. Creating an £800 pot (see fig 4.2.4.1 “Scenario A”).
fig 4.2.4.1 “Scenario A”
Then Jon bets another £300, Alex and Dave cover the bet but Mike has no more money. In this eventuality Mike still maintains a claim on the current pot but cannot win any of the addition bets that follow since he doesn’t have the money to cover them. So the £900 collected from Jon, Alex and Dave is placed in a separate pile as a side pot that only they can win (see fig 4.2.4.2 “Scenario B”).
fig 4.2.4.2 “Scenario B”
At the end of the hand all players turn over their cards.
Mike has the highest hand. Jon and Alex have equal second best hands and Dave’s hand is the third best.
The pots are then considered individually.
The £800 pot that Mike, Alex, Jon and Dave are all eligible for goes entirely to Mike, since his hand was the highest.
The £900 pot that only Alex, Jon and Dave are eligible for is split equally between Jon and Alex since their hands were the highest of the eligible players (see fig 4.2.4.3 “Scenario C”).
fig 4.2.4.3 “Scenario C”
The responsibility for implementing the side pot and split pot functionality was shared between two classes.
The BoardHands class creates a 2D array representing the value of each players hand in relation to those of the other players. How this relation translates to into a coordinate index is illustrated below.
| Code: |
[ 0 ]
^
|
| Better Hands
|
[player] ---> Equal Hands [ 10 ]
|
| Worse Hands
|
v
[ 10 ]
|
The pot class contains an array that records how many pots there are, how much is in each one and a 2D array of who the eligible players are for each pot.
I chose to use arrays over a more dynamic structure such as linked lists because I knew the maximum length and width of the array would be equal to the number of players at the table. So the flexibility of allowing for an “unlimited” number of players was unnecessary because ten players is the maximum the rules allow for. This point is illustrated below:
If every player is going for the same pot the array would look like the one below (the first row of the array is full and all of the others are empty).
| Code: |
[pot 1][player 1][player 2][...][player 10]
[ ][ ]
[...]
[ ][ ]
|
If the maximum number of split pots occurred the arrays would look like the one below (each row has one less eligible player than the previous row, until only two are left).
| Code: |
[pot 1][player 1][...][player 8][player 9][player 10]
[pot 2][player 1][...][player 8][player 9]
[pot 3][player 1][...][player 8]
[...]
[pot 9][player 1][player 2][ ][...][ ]
|
To decide how much each player has won these two data structures are compared. The comment sample below is taken from the Pot class and shows the algorithm used to share out each side pot.
| Code: |
// Pot.java --------------------------------------------------------
//Get players relative hands array.
//Get side pot and eligible players array.
//Loop through all of the side pots.
//Loop through all of the players in the relative hands array.
//Starting on the first relative hands row (the best hands).
//Check if any player in the current row of the relative
//hands array is also eligible for the side pot.
//If they are count them.
//End loop.
//Calculate how much an equal share of the current side pot
//is from its size divided by the number of players who
//have won a share.
//Again we compare the arrays.
//Loop through all of the players in the relative hands array.
//Starting on the first relative hands row (the best hands).
//Check if any player in the current row of the relative
//hands array is also eligible for the side pot.
//If they are give them a share of the side pot.
//End loop.
//End loop.
//-------------------------------------------------------------------
|
Posted Wed Dec 07, 2005 6:56 am GMT by Muck
Thanks Webby, maybe I should start using dictionary.com to confirm the meaning of a word rather than MS Word to check it existed and Google to get a straw poll of the meaning 
Posted Wed Dec 07, 2005 7:06 am GMT by wEbMaStEr
Very good....... we can direct all "Who wins this pot" enquiries to this thread 
Posted Wed Dec 07, 2005 8:38 am GMT by Muck
Or to the site I built that implements this code :D
Posted Wed Dec 07, 2005 10:15 am GMT by tame_deuces
Interesting stuff this. 
I code for a MUD (Multi User Dungeon).
For those you who weren't geeks back in the day MUDs are the multiplayer text-based forefathers of today's MMORPGs, like for example World of Warcraft.
I was thinking about coding a Hold'Em table for the players to waste their virtual money on in between dragonslaying and late night chatting. My code wouldn't have any computer opponents though.
This could come in handy if you don't mind me leeching your ideas.
Posted Wed Dec 07, 2005 12:10 pm GMT by lwestatbus
Very, very clever implementation. I especially like your Hand Comparrison Array. It both makes the winner determination algorithm and the multi-pot distribution algorithm much simpler to implement that I'd ever have imagined.
Thanks much for posting this. It was a very interesting read and a generous contribution to the forum.
Now I have to quit wasting my time and go back to grading the final I was giving when I made the posts yesterday.
Posted Thu Dec 08, 2005 5:15 am GMT by Muck
| tame_deuces wrote: | Interesting stuff this.
I code for a MUD (Multi User Dungeon).
|
I used to use a MUD to chat to mates when I was in Uni and couldn’t get IRC or IM to work
| tame_deuces wrote: |
This could come in handy if you don't mind me leeching your ideas.
|
Go for it, although an in-line comment crediting the source would be a nice sentiment
| lwestatbus wrote: |
Thanks much for posting this. It was a very interesting read and a generous contribution to the forum.
Now I have to quit wasting my time and go back to grading the final I was giving when I made the posts yesterday.
|
Thanks, pity you weren’t marking it
I figured it’s just sitting on a disk doing nothing and it’s not as if someone else couldn’t/hasn’t design their own solution.
When I develop a system to break encryption that’s when I’ll keep it to myself :D
Posted Sat Dec 10, 2005 8:30 pm GMT by JohnnyCache
For some reason I missed this completely.
This makes me want to sit down and re-install a compiler.
|
|
