Authors: David Z, Ruimou X
What is the problem?
Playing poker (Texas hold 'em) is challenging because it's not always clear what the best move is in a given game configuration. Our project aims to use Prolog to evaluate all the possible game states and determine which move is the most likely to result in success.
To do this we're modifying the game into a simpler model for exploration. We will have a list of 5 cards which will represent the hand and search for the best way to create a winning hand from those 5 cards. This is done by discarding 0-5 cards from the current hand and drawing 0-5 cards again. The program will search through all the possibilities from discard varying cards in the hand and come up with the most optimal set of cards to keep from the original hand.
What is the something extra?
The in-depth aspect involves implementing a search algorithm poker game-tree. Implementing the algorithm itself will be tricky, but creating the rules to construct the tree will be non-trivial as well.
What did we learn from doing this?
The full texas hold'em poker game is too complicated to model in this project. It involves an extremely giant game state with 2-4 players all with different hands and combinations that can result in a super large depth game tree. In searching for a solution to solve poker we came across it's massive search space through several scientific articles and programs that were far beyond the scope we thought we would deal with. Since we wanted a much smaller project that displays the abilities of prolog in this game we decided to scale the project down but kept the game so that it would allow us to generate a tree and select the best choice.
Prolog is surprisingly good at handling card substitutions with some constraints. By giving a program "free" cards prolog is able to come up with any card in the playset and try to use it in some way (in this case creating a combo out of it)
The biggest issue with prolog is that the search space is too big, it needs to check all possible cards playable as well as permutations of the cards that could lead to combos. This creates a gigantic runtime bottleneck thats difficult to work with because the language is difficult to refactor as well. In order to show our demo to the TAs we need to drastically reduce it's search space.
We also had trouble communicating state to Prolog cleanly about it's state, such as the cards that have already been drawn or how many substitutions there are in the hand so far. We also had some difficulties getting the generation to work since a predicate like number(N) just failed a free value and prevented us from ever trying numbers while member(N, [list]) did it without issue. Once we figured out how to use findall to search through all possibilties of card substitutions we were able to then attach a score to each node and select the best choice.
It's surprisingly intuitive to apply this to multiple games. One of the key features that we demonstrate is prolog's ability to generate 'options' within the constraints given, which allows it to generate the game tree. Then we used value/2 to essentially score each 'leaf' in the tree and communicated the results up. Its simple enough add additional constraints and change from cards to 'moves' and allow the program to evaluate the possibilities of every move and their results and selecting the best move instead of best replacement. The main concern is the runtime is far too slow to apply this to proper games, but it seems possible for simulations of smaller games like tic tac toe.