Do I understand it correctly that in Chess and Go it seems like DeepMind is capable of strategic thinking in a way it cannot do in StarCraft II? If yes, then how would Chess/Go need to be changed to generate the same problem?
Is it just a quantitative thing, e.g. you would make a Chess-like game played on a 1000×1000 board with thousands of units, and the AI would become unable to find strategies such as “spend a few hundred turns preparing the hundreds of your bishops into this special configuration where each of them is protected by hundred others, and then attack the enemy king”?
Or would you rather need rules like “if you succeed to build a picture of Santa Claus from your Go stones, for the remainder of the game you get an extra move every 10 turns”? Something that cannot be done halfway, because that would only have costs and no benefit, so you can’t discover it by observing your imaginary opponents, because you imagine your opponents as doing reasonable things (i.e. what you would have done) with some noise introduced for the purpose of evolution.
Arimaa is the(?) classic example of a chess-like board game that was designed to be hard for AI (albeit from an age before “AI” mostly meant ML).
From David Wu’s paper on the bot that finally beat top humans in 2015:
Why is Arimaa computer-resistant? We can identify two major obstacles.
The first is that in Arimaa, the per-turn branching factor is extremely large due to the combinatorial possibilities produced by having four steps per turn. Even after identifying equivalent permutations of steps as the same move, on average there are about 17000 legal moves per turn (Haskin, 2006). This is a serious impediment to search.
Obviously, a high branching factor alone doesn’t imply computer-resistance, particularly if the standard of comparison is with human play: high branching factors affect humans as well. However, Arimaa has a property common to many computer-resistant games: that “per amount of branching” the board changes slowly. Indeed, pieces move only one orthogonal step at a time. This makes it possible to effectively plan ahead, cache evaluations of local positions, and visualize patterns of good moves, all things that usually favor human players.
The second obstacle is that Arimaa is frequently quite positional or strategic, as opposed to tactical. Capturing or trading pieces is somewhat more difficult in Arimaa than in, for example, Chess. Moreover, since the elephant cannot be pushed or pulled and can defend any trap, deadlocks between defending elephants are common, giving rise to positions sparse in easy tactical landmarks. Progress in such positions requires good long-term judgement and strategic understanding to guide the gradual maneuvering of pieces, posing a challenge for positional evaluation.
AlphaZero did some (pruned) game tree exploration in a hardcoded way that allowed the NN to focus on the evaluation of how good a given position was; this allowed it to kind of be a “best of both worlds” between previous algorithms like Stockfish and a pure deep reinforcement learner.
This is impossible for a game with an action space as large as StarCraft II, though; but in order to modify a game like Go, it would have to become completely different.
I’m not 100% sure about the example you raise, but it seems to me it’s either going to have a decently prune-able game tree, or that humans won’t be capable of playing the game at a very sophisticated level, so I’d expect AlphaZero-esque things to get superhuman at it. StarCraft is easier for humans relative to AIs because we naturally chunk concepts together (visually and strategically) that are tricky for the AI to learn.
Pruning the game tree, or doing MC tree search, is impossible in StarCraft, not because of the size of the action space but because the game has incomplete information. At least in the standard form of those algorithms.
Do I understand it correctly that in Chess and Go it seems like DeepMind is capable of strategic thinking in a way it cannot do in StarCraft II? If yes, then how would Chess/Go need to be changed to generate the same problem?
Is it just a quantitative thing, e.g. you would make a Chess-like game played on a 1000×1000 board with thousands of units, and the AI would become unable to find strategies such as “spend a few hundred turns preparing the hundreds of your bishops into this special configuration where each of them is protected by hundred others, and then attack the enemy king”?
Or would you rather need rules like “if you succeed to build a picture of Santa Claus from your Go stones, for the remainder of the game you get an extra move every 10 turns”? Something that cannot be done halfway, because that would only have costs and no benefit, so you can’t discover it by observing your imaginary opponents, because you imagine your opponents as doing reasonable things (i.e. what you would have done) with some noise introduced for the purpose of evolution.
Arimaa is the(?) classic example of a chess-like board game that was designed to be hard for AI (albeit from an age before “AI” mostly meant ML).
From David Wu’s paper on the bot that finally beat top humans in 2015:
AlphaZero did some (pruned) game tree exploration in a hardcoded way that allowed the NN to focus on the evaluation of how good a given position was; this allowed it to kind of be a “best of both worlds” between previous algorithms like Stockfish and a pure deep reinforcement learner.
This is impossible for a game with an action space as large as StarCraft II, though; but in order to modify a game like Go, it would have to become completely different.
I’m not 100% sure about the example you raise, but it seems to me it’s either going to have a decently prune-able game tree, or that humans won’t be capable of playing the game at a very sophisticated level, so I’d expect AlphaZero-esque things to get superhuman at it. StarCraft is easier for humans relative to AIs because we naturally chunk concepts together (visually and strategically) that are tricky for the AI to learn.
So basically game tree search was the “reasoning” part of AlphaZero?
Pruning the game tree, or doing MC tree search, is impossible in StarCraft, not because of the size of the action space but because the game has incomplete information. At least in the standard form of those algorithms.
Well, it’s overdetermined. Action space, tree depth, incomplete information; any one of these is enough to make MC tree search impossible.