Look Ahead Rabbit Hole

So for a turn based game with indeterminacy, incomplete information, a high branching number, you have a few choices for AI. My fallback has always been "eh make a heuristic and call it good," but I've been reading, and I want to take a stab at doing some actual prediction and min-maxing.

For that, Monte-Carlo Tree Search appears to be the framework of choice. It has used successfully for games like Go that have heavily resisted other computerized techniques. The basic idea is that you pick a move, go a little way down, and then randomly simulate the rest of the game after having made that move. If you win more than you lose, make a note of it. Now pick a new move to test, and strike a balance between exploiting the most promising moves and exploring new moves. Each time, push your simulation a little further into the future, making it more accurate. When you're out of time, pick the best move so far. (Most visits, probably.)

So, that sounds like a good match for Legacy AI: pick a bunch of potential moves, test them out for 2-3 turns in the future, pick the best*. And since you're biased to explore the most promising moves, you make better decisions without having to thoroughly explore the entire possibility tree. One big advantage of this approach is that it requires no expert knowledge of the game domain (though it can benefit from expert-driven heuristics) in order to pick good moves. So as balance progresses, abilities are added and removed and numbers get tuned, the AI should be able to plod along more or less fine. When the game design is fairly stable, then you come back and write some heuristics to make it converge faster.

The rabbit hole is that in order to implement this, I need to be able to simulate the future in a fast and lightweight way. So, I think this means that I need changes that I apply to the game state to be reversible. Yesterday and today I've been ripping out my ChangeHandler and OutcomeProcessor classes to separate the pieces that calculate change from the pieces that actually apply the change. It's been a tricky refactor but I can tell it's making the code better overall. What used to be one big tangled mess is now just 3 unsightly contraptions. Progress.


* I have the feeling "pick the best" is going to be its own rabbit hole; scoring an outcome is not as simple in an asymmetrical game like legacy, because there's not really a binary win/lose condition for the AI, or at least, the AI is not likely to "win" by killing all the heroes and I don't particularly want it to. But in order for the algorithm to work properly some outcomes need to be preferred, so I'll have to figure out how to score playthroughs in a way that causes the MCTS to select "realistic" AI play. Should be fun.