Improving on the current MCTS can be done in a few ways that I'm interested in. The choosing of successor nodes is done purely by UCB, whereas top notch Google implementations use a deep learning approach to focus on successor nodes that seem promising. ![]() Note that this system is using a very, very vanilla MCTS approach. So while MCTS seems to be better, it still has a way to go before it is worth as an alternative to rule based systems for euchre, especially if complex rules can be used. It should be noted however that not all of these hands are equally likely especially with regards to the caller and suit picked, and so it is possible that these differences are not very important. ![]() Across all possible euchre hands this might be more noticeable. The only difference between the two is 19 situations which have a difference of 3 under the rule player and a difference of 0 under the MCTS player. So MCTS is definitely the best out of the three, but not much better than the rule implementation. The differences are the integers between 0 (no difference) and 6 (minimax gets a loner, but player implementation is euched). This is meant to show how close a given implementation comes to being optimal.īelow is a bar chart that shows the average difference between the optimal player and different player implementations.īelow is a distribution of the differences. Evaluation boiled down to replacing one of the optimal players with a given implementation and playing through the game again with all information known to all players except the player being tested. There are 1000 such annotated situations. Then I ran through this situation with an open hand (no hidden information) and Minimax players. I randomly generated various euchre situations and randomly assigned the dealer, caller, and trump suit (this is not realistic but it equalizes the negative effects amongst all players). Results were obtained as follows:įirst a test dataset had to be created. The src/deck module has definitions and helper functions for manipulating a card deck, and the src/euchre module has helper methods on top of the deck module that deal with euchre play. Each file in this module represents a different playing strategy embodied by the player interface which each file implements through a structure like SmartPlayer or RandomPlayer. These libraries are used by the different player logic found in src/player. The game agnostic AI libraries live in src/ai. Another approach could combine this minimax based approach and MCTS based on the hand, since minimax for 5 cards has a much larger search space than for 3 cards. This was actually the first thing attempted but I kinda sucked and couldn't get it to work because of non-iterative development. Weight the chosen card to be played based on the likelihood of the hands and find the average expected win value for each card. In other words, iterate over all the possible hands of opponents and run minimax assuming these hands. It seems like a combination of expected values and non-uniform random sampling may help.Īnother approach that should be attempted is minimax across randomly sampled hands. For actual play, a MCTS algorithm has been used with some success, but it remains to be seen how to elevate it above human ability. It is not known whether these samples are linearly separable, so it remains to be seen whether some SVM or more complex model must be created to perfectly separate picking up from not picking up. ![]() Given some training set of the game state on reaching the AI, the perceptron will mold to match this input using 11 predefined features. The AI algorithms in use now or that have already been implemented but are not currently in use are the perceptron for picking up cards and calling suit. So it should be fun, let's see what happens! The software will try to compare two several different approaches, several different AI methods, a rule based method, and a random method. This is a learning experience and as such, I've also chosen to use golang to implement it. An attempt to create a euchre playing AI.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |