Link to the actual paper: http://julian.togelius.com/Justesen2016Online.pdf http://julian.togelius.com/Justesen2016Online.pdf I've written an AI for a similar

Link to the actual paper: http://julian.togelius.com/Justesen2016Online.pdf http://julian.togelius.com/Justesen2016Online.pdf I've written an AI for a similar game, where you can't always even iterate over all your moves for this turn, let alone do a multi-ply tree search. Using their terminology of Action and Turn, my method was to first evaluate individual Actions using a simpler evaluation function, and apply a cutoff so that only a reasonably number of Actions had to evaluated, then combine that reduced group of Actions together to make a reasonable subset of full Turn moves, then use the full evaluation function to find the best Turn. Writing a good evaluation function for a complex game is hard, so I picked a whole bunch of inputs and then used a genetic algorithm to find weights for them. (Let the various AIs play entire games, and let the winners breed.) Works okay, but still can't beat a decent human player very often. (There's enough randomness in the game that the better player doesn't always win.) In this paper, their Online Evolution beat the other four computer strategies, but they don't mention whether it can beat good human players. If it can't, it's not clear to me whether Online Evolution is a good algorithm. Beating their other four algorithms doesn't seem to be a very high bar.