Nearest neighbor doesn't scale that well.
If you consider partial game states (eg, player A's turn on game y), then there are about 80 million game states (2 M games * 40 player turns/game) on councilroom. I love you guys, but I sure as hell am not going to be scanning 80M rows very often ;P.
The metric is everything and it's hard to come up with a good one by hand. If you are going to learn the metric, why not just learn the function directly?
But yeah, I think that learning the chance of winning as a function of the game state is a super interesting/useful thing to do. I'll happily give you shell access to councilroom to help you experiment.
Alternatively, you could try to beat the algorithms on the dataset here:
http://mlcomp.org/datasets/872
Though that is doing classification (predict winner) rather than regression (predict probability to win).
Wow, that is impressive.
My objective was much less ambitious: just put a metric on the initial state of the game (that is, the 10 kingdom cards) and essentially have a button on council room "find closest games". Then you could use these sample "similar" games to get an idea of how long the game should last, what good strategies others have come up with, and so on. Plus you could do some kinds of statistics on average turns and average points to guide your decision making.
And as Jimm suggested, the approach I took for that was first to introduce a metric on cards. I automated that rather than filled in all the 128x128 coefficients matrix by hand. Just plug in all the characteristics of the cards (+2 actions, card type, gold given, "special powers", "cursing" and so on) and fit some kind of intuitive function until you get a matrix that looks right to you.
Normalize it into a correlation matrix, then write down each kingdom as a 128 dimensional vector and correlate kingdoms. A correlation of 1 is then equivalent to having an identical pool.
This ignores non-linear effects, like gardens being more powerful in combination with workshop, which is a big problem. But it makes for very fast computing, because the correlation matrix only needs to be computed once, and then you just go through your database of games, correlating them to the kingdom you are studying.
distance <- function(card1, card2){
d = 0;
if(card1!= card2){
d = d + 2 * abs(allcards[["Cost"]][card1]- allcards[["Cost"]][card2]);
d = d + 3 * abs(allcards[["Actions"]][card1]- allcards[["Actions"]][card2]);
d = d + 3 * abs(allcards[["Cards"]][card1]- allcards[["Cards"]][card2]);
d = d + 4 * abs(allcards[["Action"]][card1]- allcards[["Action"]][card2]);
d = d + 4 * abs(allcards[["Victory"]][card1]- allcards[["Victory"]][card2]);
d = d + 4 * abs(allcards[["Treasure"]][card1]- allcards[["Treasure"]][card2]);
d = d + 5 * abs(allcards[["Attack"]][card1]- allcards[["Attack"]][card2]);
d = d + 1 * abs(allcards[["Reaction"]][card1]- allcards[["Reaction"]][card2]);
d = d + 3 * abs(allcards[["Duration"]][card1]- allcards[["Duration"]][card2]);
d = d + 2 * abs(allcards[["VP"]][card1]- allcards[["VP"]][card2]);
d = d + 1 * abs(allcards[["Coins"]][card1]- allcards[["Coins"]][card2]);
d = d + 1 * abs(allcards[["Buys"]][card1]- allcards[["Buys"]][card2]);
d = d + 1 * abs(allcards[["Gain"]][card1]- allcards[["Gain"]][card2]);
d = d + 7 * atan(abs(allcards[["Trash"]][card1]- allcards[["Trash"]][card2]));
d = d + 6 * atan(abs(allcards[["Pollute"]][card1]- allcards[["Pollute"]][card2]));
d = d + 3 * abs(allcards[["Combo"]][card1]- allcards[["Combo"]][card2]);
d = d + 3 * (allcards[["Special"]][card1] + allcards[["Special"]][card2]);
d = d + 3 * abs(allcards[["Discard"]][card1]- allcards[["Discard"]][card2]);
d = d + 1 * abs(allcards[["Cycle"]][card1]- allcards[["Cycle"]][card2]);
d = d + 100 * abs(allcards[["Win"]][card1]- allcards[["Win"]][card2]);
}
return(d);
}
This is in R the function I currently use to give a metric between cards. All the types until buys are standard. "Gain" stands for cards that can cheat their way through the 1 buy rule to gain a card (remodel, upgrade...). I gave that the same importance as a buy. Trash is how many cards the selected card can trash. Pollute is when it makes the other player gain cards in some way. Combo is basically a general term for "this card works well in action heavy decks". Anything that intuitively fits with conspirator goes in there. "Special" is a category that says that the effect of this card is unique (think: goons or gardens) and just creates distance between it and any other card. Discard is anything that reduces your opponent's hand size in some way (militia, minion, bureaucrat...). Cycle is any effect that enables you to cycle hands from your card for any kind of effect (vault, cellar, hamlet...) and win is the win rate of a card as measured by the councilroom stats.
I'd post the correlation matrix I get, except it's big and ugly. For fun, the two closest non-identical cards are apparently worker's village and farming village (0.81 correlation).
I'm sure the above formula needs to be refined a lot. That being said, I like this approach because it taps into this huge database of games we have and complements nicely the simulation approach.