I know there are fighting games where the final boss AI is considered impossibly tough but that’s almost always because the AI final boss has both buffed health/attack but also isn’t subject to the same restrictions to the player, as in they can input combos instantly and they also will “read” player inputs and immediately counter them.
Similarly there’s “tough” AI in strategy games but in those games the AI also tends to be given resource buffs and is allowed to see through the “fog of war” and look at your unit builds and unit locations and decide how to counter based on that.
So are there any AI’s made for a video game that are actually set to the same restrictions a human player has to abide by that can beat a top human player 75% of the time much like with chess?
An AI called deepmind can now beat 99% of human players on Starcraft II, one of the big esports games. The paper on it was on the front cover of Nature last year.
Don’t know if you could say it had ‘solved’ the game as it seems too open-ended for that, but the problem was rated as orders of magnitude more difficult than solving chess.
Eh, even if you restrict the machine to the limits of human-used input devices, its reflexes are still going to be far better than any human’s. That right there makes video games more amenable to AI than turn-based games like chess.
It’s not named deepmind, Deepmind is a London-based Alphabet subsidiary that works on AI and Machine learning. It’s called AlphaStar (even though the algorithm has little relationship to AlphaGo, the solver that can beat the world’s best in Go).
There are actually a lot of difficulties:
Partial information increases complexity dramatically.
The action space for Starcraft is bonkers (since you can theoretically send any unit to any tile on the map at any time, in multiple different ways).
It’s not entirely clear how to model the input space (just the screen is likely insufficient because the AI can’t read current resources and such from text like a human can).
They solved all of these problems, but it was incredibly nontrivial and took a long time.
It’s my understanding that the Starcraft II bot did rely on superhuman reflexes quite a bit. Yes, the actions per minute was capped, but the bot could “micro” at a superhuman level. That is, it could do things like micromanage units to jitter around, run into and out of combat, and do other things that vastly increase combat performance and would be impossible for a human to do at the same speed. That is alluded to in the Nature paper.
At one point the bot was also given visible access to the whole map rather than just what would be visible for a human so it didn’t have to move the camera around to keep track of things.
I don’t follow this particular development very much, but I believe the micro issue was present when Alphastar declared victory and stopped development. I wouldn’t call Starcraft solved quite yet.
Yeah, AlphaStar didn’t APM like a beast, but rather benefited greatly from instant unit selection (and always picking the right unit at the right moment.) It used a simple strategy (Stalker spam) and bullied the human player Mara with unobtainable macro and micro gameplay.
The whole thing is dumb. Of course humans can build a machine that does something better than a human could. That’s the story of our entire existence.
On the other hand, was stalker spam the only strategy the AI was capable of, or was it simply the first strategy it tried that worked, and never needed to improve further because there was no selective pressure to do so? I mean, if stalker spam with superhuman reflexes is good enough to consistently win, and you have superhuman reflexes, then why not use stalker spam?
Though they should at least have come up with a strategy for each of the three races. This would enable a computer to play as “random”, and pick the appropriate one for whatever it ended up with, and would also give them a rudimentary ecosystem in which to test and train the AIs against each other.
There appears to be a belief that RTS games like Starcraft would be a harder challenge for computers than turn-based games like Civ. I have never understood that precisely for the reasons that you identify that the computer would have an obvious advantage with hyper-precise unit selection and control.
I would like to see AI being deployed on games like Civ. They could start of with a standard map and one-on-one play and go on from there. I am guessing that it would be a much bigger challenge than Go.
Can’t believe I’m the first pedant, but “solved” has a specific meaning in game theory; it means a mathematically optimal strategy has been found.
Tic tac toe has been solved; the game is a draw with perfect play by both sides. The same is true of checkers. Connect Four is also solved but in that game the first player can force a win with correct play.
Chess is not solved. At the top level of human and computer play, draws are common, and it seems likely to be drawn with best play by both sides, but we don’t know (and may never).
But yes, from the description, the OP means whether an AI playing fairly against an expert human can win, and yes chess is solved by this meaning. Indeed the very best chess computers are as much as 600 ELO above the world’s best players, which in laymen’s terms means it’s not even close.
Well, they could restrict the bot to interact with Starcraft with cursor vs having direct individual control of units. They throttled APM to level the playing field, but they are AI researchers, not Starcraft SMEs. I’m sure they could make a level playing field, but from Deepmind’s perspective they might have learned what they could and don’t see the need. The goal was to learn about ML techniques applied to real time partial information games, afterall. Starcraft is merely a means to that end.
I was thinking about AI for Civ 4 the other day. Being turn-based does eliminate the need to creatively level the playing field. It does have some pretty interesting aspects: partial information (fog of war), multiplayer, long time horizon (AIs have had a lot of trouble for long term goal planning), and multi-objective (there are multiple ways to win). I’d absolutely love to see an approach to this.
Civ is turn-based, but it adds another major complication: Alliances and agreements (which will inevitably eventually be re-negotiated or broken) are a fundamental part of the game, which in turn means knowing whom to trust, and for how long (and when to move such that opponents will no longer trust you). All the more so, in that if the opponents know that you’re an AI (or even just that you’re a particularly strong player), they might be more inclined to all gang up on you. And no amount of skill at the game, natural or artificial, is going to be able to overcome seven others whose first priority is making sure you don’t win. The only way to win consistently is to consistently convince the other players that you’re not the greatest threat.
In fact diplomacy seems such a complicated problem that I would imagine it would have to be largely removed in early versions to give the AI any chance at all, perhaps by sticking to two player games.
What remains is the task of harmoniously managing complex sub-systems in the pursuit of a very long-term goal. A good Civ player has a rough plan for their entire game of hundreds of turns up to the specific victory type they are aiming for. They have a deep understanding of the long-term consequences of seemingly minor early decisions like city placement. At the same time they have to be flexible about the details. I would imagine all this would be huge problem for AI and at the same time progress in these areas would be useful in a range of real-world problems too.
So I am a bit surprised that AI researchers haven’t explored Civ more, particularly since I would bet a bunch of them are fans.
‘Go’ is not solved but an AI has defeated a top human player.
Another interesting AI opponent quirk is they can sometimes see slightly (a single turn) into the future. When “random” events appear to affect the player unfairly compared to the AI this is usually what is happening. The AI can’t stop the event but it can make the best choice available to it a turn sooner than you can.