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.
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.