|
I am interested in the card game Dominion. I have scraped about 300,000 game logs from an online Dominion server. I want to be able to estimate the probability of winning for each player in the game given a partially played game. With this information, I can identify critical turns (big changes in win probability per player) and possibly create an AI that plays the game. From 20,000 feet, at the start of the game, 10 cards are picked from a set of 120. From then on, 10 copies of the initial 10 cards are used for the rest of the game, with 6 additional cards that appear in every game. As the game goes on, players accumulate these cards into their deck through a sequence of around 20 turns. Players tend to get around 1 or 2 cards per turn. The game state can be encoded into a feature vector of about 130*3 integers between 0 and 10 (the available cards left, the number of each card owned by player 1, and the number owned by player 2). Most of the cards are unavailable, so about 90+% of the data is going to be 0. If I encoded the game state after each turn, there would be about 20 turns/game * 300k games * 2 players / game ~= 12 million training instances. Is there any general things that I should know about applying machine learning to prediction from game logs? Are there any algorithms or open source tools that I should apply to this problem? In general, I am biased in favor of Python. |
|
The problem, if I understood you right, is to build a classifier that will predict, given a partial game, how the game will end. I'd start by setting up an experimental setup: get a large enough subset of the games (maybe half), split it into a training and test set, and record the state of the game after a constant K number of plays to use as the instances and the result of the games to use as the labels. If you build a good classifier in this setting you might later try to extend it to the harder problem of always estimating good win/lose probabilities over the game (it is harder because if you split each game in a random point you might throw away a lot of data and if you include training examples for all games at all stages of play you get a very non-iid training set which might confuse some learning methods). After setting up your experimental environment you should think about how to train such a classifier. For ease of testing and implementation I suggest you start with a linear model such as regularized logistic regression (which has the nice property of always giving you calibrated probabilities as its output). This reduces your problem to picking out good features that you expect are correlated or anti-correlated with the outcome of the game. Some obvious features are a player's cards, the other player's cards, possible features for pair of cards, features for how these cards were used so far, etc. After deciding on a set of features for a game, train a classifier and inspect their weights. Features with weights close to zero are irrelevant, and features with high (both very positive and very negative) weights are really influential. If some feature you think is important is getting a small weight, think if there's any interaction you should model that can improve its predictive power. In python you can do all these things using scikits.learn, which has efficient implementations of logistic regression, feature extraction, experimental pipelines, etc. The point about picking only state per game to avoid correlation in the sampling is interesting. From playing the game myself, card pairs/triples are very important. Am I correct in understanding that a linear model isn't going to consider pairs of input features directly, so that I'd need to include them as features in the input itself? Would something like an SVM with a polynomial kernel of degree 2 or 3 do a better job at considering pairs/triples of features in the input without exploding the feature space?
(Feb 01 '11 at 19:40)
Rob Renaud
1
Yes, an SVM with a polynomial kernel will explore feature combinations automatically. The downside is that it will do that as a black box, and you will have no idea in the end why your model is or isn't working, and how to improve it, without many experiments. With linear models you can control how and which combinations you introduce, and you can understand which work and which won't, and this sort of insight when you're starting can be very useful. Later on, after discovering a good structure for your problem and thinking about how to generalize to the whole game, you should probably switch to random forests, boosted decision trees, or svms to improve performance.
(Feb 01 '11 at 19:44)
Alexandre Passos ♦
|
Just one thought: You may want to address the symmetry of participants in the game somehow. Often in such problems, a predictive model is built in which (about) one half of the input variables pertain to one player, and the other half apply to the other player. One would hope that, were the player's positions in the model reversed, that the probability of each of them winning would reverse.
In some competitions there is a natural and relevant asymmetry which can be exploited. For instance, in most team sporting events, one team is at "home", while the other is "away". In the model, the home team would always occupy one half of the predictors, while the away team would occupy the other half.