Excellent question! Once again, late to the party, but here are my thoughts:
It’s very hard to come up with any board game where humans would beat computers, let alone an interesting one. Board games, by their nature, are discretized and usually perfect information. This type of game is not only solved by AI, but solved by essentially a single algorithm. Card games with mixed strategy equilibrium like Poker do a little better, although Poker has been solved the algorithm doesn’t generalize to other card games without significant feature engineering.
If I were to design a board game to stump AIs, I would use these elements:
Incomplete information, with the possibility of information gathering (“scouting”) at a cost (like in Starcraft 2) to invalidate Markov property
Lengthy gameplay (number of moves) to make the credit assignment problem as bad as possible for RL agents
Patterns that require abstract reasoning to discern (e.g. the pigeonhole principle lets you conclude immediately that 1001 pigeons don’t fit in 1000 pigeonholes; an insight that can’t practically be learned through random exploration of permutations)
The last element in particular is a subtle art and must be used with caution, because it trades off intractability for RL against intractability for traditional AI: If the pattern is too rigid the programmer could just hard-code it into a database.
If we considered video games instead, the task becomes much easier. DOTA 2 and Starcraft 2 AIs still can’t beat human professionals at the full game despite the news hype, although they probably can beat the average human player. Some games, such as Chronotron or Ultimate Chicken Horse, might be impossible for current AI techniques to even achieve average human level performance on.
In addition to your ideas, I would add long tales and chaotic systems. It’s hard to train an AI on 1,000,000 datapoints when the value function of the 1,000,001st datapoint could outweigh all the previous cumulative results.
To generalize this mathematically, a board game ought to have a value function that never converges no matter how many times you play the game.
Thanks a bunch Maxim! I remember you in my hypothetical “drop all water on Earth” question—so, a usually late guy but always arrives with excellent answers :)
1 of the main differences between board & card games that I can discern is that 1 has perfect info, as you pointed out, the other not. Thus if we integrate imperfect info into a board game, can programmers just combine the 2 algorithms to solve it, or they will have to find another approach?
Unlike the Earth water question, I have some difficulties understanding the technical terms fully:
I don’t really know SC2 but played Civ4, so by ‘scouting’ did you mean fogbusting? And the cost is to spend a unit to do it? What does it have to do with Markov property? Is fogbusting even possible in a real life board game?
Lengthy gameplay, IMHO, is bad when our 2nd goal is to attract people. Especially in this age of distraction, where youngsters can’t concentrate for 20 minutes.
I learnt in a Crash course that computer science is essentially many layers of abstracting, so I’m a bit surprised when it turns out that AIs can’t see the obvious 101 pigeons in 100 holes. Can we conclude that what separate us humans from AIs is that ability of insight? Also, I’m curious as to how you’d apply this last element in a real game example.
BTW, what is RL? Real-life? :)
Video games has some advantages regarding AI over board games. While boards are restricted by real life physics & amount of materials (1 can’t have 9 pawns in chess!), software offers virtually endless options & things to add. The amount of variations & positions are also tremendous, thus brute force is inefficient. The examples you linked show that. Therefore, it is in board games that we have to apply our ingenious the most to fuck those AIs up.
I don’t really know SC2 but played Civ4, so by ‘scouting’ did you mean fogbusting? And the cost is to spend a unit to do it? Is fogbusting even possible in a real life board game?
Yes. There has to be some cost associated with it, so that deciding whether, when and where to scout becomes an essential part of the game. The most advanced game-playing AIs to date, AlphaStar and OpenAI5, have both demonstrated tremendous weakness in this respect.
What does it have to do with Markov property?
Markov property refers to the idea that the future only depends on the current state, thus the history can be safely ignored. This is true for e.g. chess or Go; AlphaGoZero could play a game of Go starting from any board configuration without knowing how it got there. It’s not easily applicable to Starcraft because of the fog of war; what you scouted inside your opponent’s base a minute ago but isn’t visible right now still provides valuable information about what’s the right action to take. Storing the entire history as part of the “game state” would add huge complexity (tens of thousands of static game states).
Is fogbusting even possible in a real life board game?
RL stands for reinforcement learning, basically all recent advances in game-playing AI has come from this field and is the reason why it’s so hard to come up with a board game that would be hard to solve for AI (you could always reconfigure the Turing test or some other AGI-complete task into a “board game” but that’s cheating). I’d even guess it’s impossible to design such a board game because there is just too much brute force compute now.
Ah, I see. All of your explanations led to 1 thing: imperfect information. Fogged Markov tiles or coin-like tokens are ways to confuse AI and force it to ramp up the brute power exponentially without much effort from the puzzler &/or much effect in game. And since it doesn’t know the info, it can’t accurately calculate the value of that info, that’s why AI sucks at scouting.
Coincidently, I’ve already invented a board game that incorporates imperfect info to beat AI back in 2016. I guess I’d need to put some more into it.
I think I have found an example for my third design element:
Patterns that require abstract reasoning to discern
The old Nokia game snake isn’t technically a board game, but it’s close enough if you take out the reaction time element of it. The optimal strategy here is to follow a Hamilton cycle, this way you’ll never run into a wall or yourself until the snake literally covers the entire playing field. But a reinforcement learning algorithm wouldn’t be able to make this abstraction; you would never run into the optimal strategy just by chance. Unfortunately, as I suggested in my answer, the pattern is too rigid which allows a hard-coded AI to solve the game.
Excellent question! Once again, late to the party, but here are my thoughts:
It’s very hard to come up with any board game where humans would beat computers, let alone an interesting one. Board games, by their nature, are discretized and usually perfect information. This type of game is not only solved by AI, but solved by essentially a single algorithm. Card games with mixed strategy equilibrium like Poker do a little better, although Poker has been solved the algorithm doesn’t generalize to other card games without significant feature engineering.
If I were to design a board game to stump AIs, I would use these elements:
Incomplete information, with the possibility of information gathering (“scouting”) at a cost (like in Starcraft 2) to invalidate Markov property
Lengthy gameplay (number of moves) to make the credit assignment problem as bad as possible for RL agents
Patterns that require abstract reasoning to discern (e.g. the pigeonhole principle lets you conclude immediately that 1001 pigeons don’t fit in 1000 pigeonholes; an insight that can’t practically be learned through random exploration of permutations)
The last element in particular is a subtle art and must be used with caution, because it trades off intractability for RL against intractability for traditional AI: If the pattern is too rigid the programmer could just hard-code it into a database.
If we considered video games instead, the task becomes much easier. DOTA 2 and Starcraft 2 AIs still can’t beat human professionals at the full game despite the news hype, although they probably can beat the average human player. Some games, such as Chronotron or Ultimate Chicken Horse, might be impossible for current AI techniques to even achieve average human level performance on.
In addition to your ideas, I would add long tales and chaotic systems. It’s hard to train an AI on 1,000,000 datapoints when the value function of the 1,000,001st datapoint could outweigh all the previous cumulative results.
To generalize this mathematically, a board game ought to have a value function that never converges no matter how many times you play the game.
Thanks a bunch Maxim! I remember you in my hypothetical “drop all water on Earth” question—so, a usually late guy but always arrives with excellent answers :)
1 of the main differences between board & card games that I can discern is that 1 has perfect info, as you pointed out, the other not. Thus if we integrate imperfect info into a board game, can programmers just combine the 2 algorithms to solve it, or they will have to find another approach?
Unlike the Earth water question, I have some difficulties understanding the technical terms fully:
I don’t really know SC2 but played Civ4, so by ‘scouting’ did you mean fogbusting? And the cost is to spend a unit to do it? What does it have to do with Markov property? Is fogbusting even possible in a real life board game?
Lengthy gameplay, IMHO, is bad when our 2nd goal is to attract people. Especially in this age of distraction, where youngsters can’t concentrate for 20 minutes.
I learnt in a Crash course that computer science is essentially many layers of abstracting, so I’m a bit surprised when it turns out that AIs can’t see the obvious 101 pigeons in 100 holes. Can we conclude that what separate us humans from AIs is that ability of insight? Also, I’m curious as to how you’d apply this last element in a real game example.
BTW, what is RL? Real-life? :)
Video games has some advantages regarding AI over board games. While boards are restricted by real life physics & amount of materials (1 can’t have 9 pawns in chess!), software offers virtually endless options & things to add. The amount of variations & positions are also tremendous, thus brute force is inefficient. The examples you linked show that. Therefore, it is in board games that we have to apply our ingenious the most to fuck those AIs up.
Yes. There has to be some cost associated with it, so that deciding whether, when and where to scout becomes an essential part of the game. The most advanced game-playing AIs to date, AlphaStar and OpenAI5, have both demonstrated tremendous weakness in this respect.
Markov property refers to the idea that the future only depends on the current state, thus the history can be safely ignored. This is true for e.g. chess or Go; AlphaGoZero could play a game of Go starting from any board configuration without knowing how it got there. It’s not easily applicable to Starcraft because of the fog of war; what you scouted inside your opponent’s base a minute ago but isn’t visible right now still provides valuable information about what’s the right action to take. Storing the entire history as part of the “game state” would add huge complexity (tens of thousands of static game states).
Yes, hidden identity chess for instance.
RL stands for reinforcement learning, basically all recent advances in game-playing AI has come from this field and is the reason why it’s so hard to come up with a board game that would be hard to solve for AI (you could always reconfigure the Turing test or some other AGI-complete task into a “board game” but that’s cheating). I’d even guess it’s impossible to design such a board game because there is just too much brute force compute now.
Ah, I see. All of your explanations led to 1 thing: imperfect information. Fogged Markov tiles or coin-like tokens are ways to confuse AI and force it to ramp up the brute power exponentially without much effort from the puzzler &/or much effect in game. And since it doesn’t know the info, it can’t accurately calculate the value of that info, that’s why AI sucks at scouting.
Coincidently, I’ve already invented a board game that incorporates imperfect info to beat AI back in 2016. I guess I’d need to put some more into it.
I think I have found an example for my third design element:
The old Nokia game snake isn’t technically a board game, but it’s close enough if you take out the reaction time element of it. The optimal strategy here is to follow a Hamilton cycle, this way you’ll never run into a wall or yourself until the snake literally covers the entire playing field. But a reinforcement learning algorithm wouldn’t be able to make this abstraction; you would never run into the optimal strategy just by chance. Unfortunately, as I suggested in my answer, the pattern is too rigid which allows a hard-coded AI to solve the game.