Authors: Thomas Roche, Aaron Mishkin
What is the problem?
Poker is a popular multiplayer game with many variations. Building a simple program that can play a reduced form of poker against a human player is a challenging problem with many interesting elements. The reduced form of poker that will be considered is as follows:
There are two players. Both players begin the game with an equal sum of money. The game consists entirely of individual "hands" that are played until one player runs out of money or quits. In a single hand, each player is first dealt a five cards. The players then independently bet a sum of money from the amount that they possess on the chance that they will win the round. Victory in a round is determined by the quality of the players' hands; the player with the best hand wins, where the best hand is determined according to the basic rules of poker. The winner of the round keeps both bets, while the loser gets nothing.
It is clear that creating a program to play this version of poker requires that the games' rules be represented carefully and meaningfully. This representation must include a compact method of comparing poker hands based on hand types and card ranks. The stochastic elements of poker must also be addressed by the program. All different types of poker share two main stochastic elements: card selection, and the actions of other players. Cards are selected randomly from a deck of 52 distinct cards to form hands, which typically range from 2-5 cards in number. So, any poker playing program must include a system for generating random poker hands by sampling from a card deck without replacement. Addressing the stochasticity arising from the actions other players is extremely complex and the focus of research at many top institutions. It is beyond the scope of this project. Creating the program also obviously requires the development of a rudimentary user interface that will allow users to play against the program.
A description of the rules of poker can be found here: http://www.contrib.andrew.cmu.edu/~gc00/reviews/pokerrules.
What is the something extra?
The something extra is the attempt to develop an effective policy that an artificial agent may follow when playing this game against a person. This policy should follow from the rules of the game and must be computed efficiently enough to be used. It should also be simple. There are many powerful tools in AI for solving problems like this one (Partially Observable Markov Decision Networks for example), but they are sophisticated in both computation and concept and using such models should be avoided if more straightforward solutions exist.
What did we learn from doing this?
Overall, logic programming was very suitable for creating a reduced poker game with an artificial agent. The tasks required to complete the project can be divided up into three main areas: representing the rules of poker; creating the user interface; and implementing the reduced poker game itself.
The rules of poker are clearcut and easily representable. The different types of hands all have distinct values on an ordinal scale. In the case of ties, there is a clear system for determining the best hand based on the ranks of the cards within it. These rules were easy to naturally represent in Prolog. However, it was not trivial to go from these rules to a system for computing a single score value for every given hand as is needed to allow easy comparison between hands. This single score value also proved deeply useful for creating an artificial agent that could play the game. Thankfully, accurate methodologies for computing scores from poker hands had already been developed, although not in Prolog. The system that this project uses is based on one presented by Shun Yan Cheung of Emory University (see below).
Implementing the user interface of the reduced poker game was much more difficult than representing the rules of the game. Prolog does not seem designed to accept user input and console-based interfaces that can be easily created using Prolog are not very usable. Significant issues were encountered dealing the problems of the following form:
Examine the following rules for play_again(User_Winnings, Computer_Winnings), which are intended to elicit from the user whether not not they want to play again.
play_again(User_Winnings, Computer_Winnings) :- User_Winnings > 0, write("Do you want to play another hand? (yes), (no)\n"), read(yes), new_game(User_Winnings, Computer_Winnings).
play_again(User_Winnings, Computer_Winnings) :- User_Winnings > 0, write("Do you want to play another hand? (yes), (no)\n"), read(no), write("Goodbye!").
Notice that one rule is true when the value "yes" is read from the console (user input) and the other is true when "no" is read from the console. While these rules may appeared to be fine, they actually cause the user to be queried twice when they do not want to play again (i.e. the input is "no"). The source of the problem is that Prolog's pattern matching is not applied to the body of the clause. This means that one rule is chosen first, and if it fails because the input read from the console does not match the constant given, the next rule is chosen. The result is that the user is queried twice and must input the same answer both times. While such an issue may seem trivial, it was both difficult to discover and serves well to highlight the difficulties of building a user interface using Prolog.
Implementing the reduced poker game was not easy, but it was well suited to logic programming. The game is based on hard, inviolable rules that were easily represented as predicates. For example, the rules of the game state that one player bets, then the next player bets, and then the hands are compared to determine the winner. This lends itself well to translation into a predicate on two players, their cards and money, and a winner, that is true when both players have bet, and the winner is the player with the better (higher score) hand. Most elements of the reduced poker game, such as generating hands of cards for each player, managing eliciting and managing bets, and starting new "hands" (instances) of the game could be and were represented in a similar manner.
The hardest aspect of the representing the game was building a simple decision making system for the artificial agent that allowed it to make reasonable bets according to the quality of its hand. This was accomplished by translating scores for poker hands into bets based on the amount of money the computer could bet, and the size of the user's bet. The arithmetic is fairly simple:
Computer Bet = floor((Computer_Money * (Hand_Score / Max_Score)) + Player_Bet * (1 / 10))
In general, the system above works well for generating bets for the artificial agent. It consistently generates reasonably sized bets that prevent the agent from losing too much money on bad hands, but still allows it to capitalize on good ones. However, it can be gamed quite easily by the user. For example, the agent can be slowly bankrupted if the user bets exactly one dollar every hand; the agent always bets based on the value of its hand rather than the size of the user's bet. Another issue is that the likelihood of either the user or artificial agent being dealt a good hand of cards is very low because the reduced game has no mechanism for card switching. The result is that the value of the agent's bets remain within a specific range most of the time, providing another mechanism for user's to take advantage of.
In summary, logic programming was a good choice for implementing a rule-based game like poker, although some aspects of the project, like user input, were not well suited to some of Prolog's design choices.
We learned a great deal working on this project. Our knowledge of Prolog has deepened a great deal and we are now familiar with some of the predicates provided by Prolog's standard library. Additionally, we learned a great deal about the limitations of game playing agent's based entirely on simple rules. These agents are easily gamed, and do not account for many of the subtleties of the games they are designed to play.
Conversion System - http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/10/pokerValue.html