EPTSumary:
+ Show Spoiler +
An artificial intelligence cannot count on intuitions and experiences, e.g. about how physics works, to draw conclusions about game mechanics. Even if it could, it cannot interpret the pixel data without being given any pointers. The reason why we are better at games is because we draw from many different components. So a good A.I. bot should do the same.
My last post in the series dealt with human intelligence and how humans work.
I finished with the following outlook: “In a next post, I will attempt to map the cognitive capabilities to attributes of an artificial intelligence, compare strengths and weaknesses and hopefully lay out a road map to cover current deficiencies of bots.”
Before getting to that, let’s start with a guide on how to not think like a human
Section 1: How to not think like a human
Sometimes we may ask ourselves why machines are so bad at doing something that seems so easy to us. A well-known blogger asks why a machine needs tens of thousands of iterations evolving a neural net to play something as simple as a game of pong. After all, we humans are able to learn the game within just a few minutes.
In my opinion such questions are based on a misconception. Most notably our tendency to think that we are smarter than we actually are. Our brain is not the general-purpose intelligence machine you may think it is. In fact, it is very optimized for problems and situations that are expected to occur in nature. Our brain also takes a lot of shortcuts to get great results in most of the cases. A well-tuned heuristic approach, so to speak. Those shortcuts however, come at a cost. This is best visualized via a wide range of optical illusions, which mercilessly exploit said shortcuts to trick us into viewing something that isn’t there.
Another very sensible shortcut we take is the fact that we come pre-equipped with a physics engine. 6-month-old babies already understand basic concepts such as the law of inertia or simply the fact that if an object is there now, it will probably still be there in a second.
Here comes the second misconception: games like pong (actually I would bet almost any game we have invented) are not necessarily easy, but follow a specific set of rules that is very familiar to us humans. If you press “up” on your controller, your pong bad will move up. If you press it again, it will still go up. If the pixels representing the ball are in the middle of the screen now and were a bit to the left a second ago, they will probably shift a bit to the right in the future, because the ball movement is simulated to follow a physical law and keeps its direction until it hits an obstacle.
Now take a step back and imagine a game of pong which does not follow any rules we already knew as a baby. Let’s say the ball just appears anywhere on the screen in a pattern that is predictable, but very hard to spot. Would we still fare better than the A.I. programs? Certainly not. In fact, the machine would probably beat us to finding such an unnatural pattern.
If we want to understand the challenges of A.I., for example in the field of Brood War, we must think like a machine. When a machine is fired up for the first time it knows nothing. Absolutely nothing at all. No wonder a neural net takes a very large number of iterations to become good at a particular task if it has to rediscover all of nature’s laws via trial and error first, right?
Let’s apply this line of thinking to Brood War and ask some questions that seem silly to us, because we instantly know the answer:
- What choke on the map should I protect with my units before I expand to my natural? What’s a choke anyways?
- If my win condition is to have zero enemy buildings on the map, why should I mine minerals first? (LetaBot, winner of the SSCAI tournament 2016, doesn’t know the answer to this one either :p)
- How could a map with very short rush distances potentially influence the game?
- So the opponent just stole my gas. What do I do now?
Now try answering these questions imagining you have no previous understanding whatsoever and start with a blank state.
Let's pick the rush distance as an example: Without knowing or having an intuition about s = V / s (time = speed / distance) how could you possibly connect the dots to conclude that a shorter distance between bases will make the enemy units arrive sooner? Remember the A.I. doesn't know anything unless it is told! (you don't want your bot to have to rediscover classic physics on its own every time you start it...)
Recently I saw an old edition of Brood War “pimpest plays”. Video: + Show Spoiler +
At the 2 minute mark the zerg player needs gas, but his last drone is threatened by a Wraith. The impressive solution is to repeatedly use dark swarm to protect the drone from the Wraith, escorting the drone step by step all the way to the geyser. How did the human player come up with this creative solution? He did the following reasoning within seconds:
- Opponent has a Wraith, I need to counter with a Scourge
- I need gas to train a Scourge, but I don’t have any
- I need to mine gas, so I have to send a drone to the geyser
- There is only one drone left, so send it
- The drone is being attacked by the Wraith and will likely die before it reaches the geyser
- I can protect the drone from ranged Wraith attacks by using a Dark Swarm
- For Dark Swarm I need a Defiler. I happen to have one, so I use it
- I cast the Dark Swarm in a way such that the drone can close the distance to the geyser
- Further Dark Swarm spells are required to cover the remaining distance, but the defiler doesn’t have any energy
- Consume a Zergling to regain energy
- Cast another Dark Swarm and repeat the procedure until the drone reaches the geyser
How will a bot ever be able to devise such a plan? Note that the concept of covering something from the vision of a third party is very natural to us. It is part of the physics engine we are hardwired to intuitively understand, just like the relation between distance, speed, and time. It also makes intuitively sense that melee units can still attack in a Dark Swarm, but ranged units can’t. But a bot has none of this knowledge and experience at its disposal. It needs to understand what the spell does and how it can be applied without being able to base such learning on its intuition of how things are supposed to work.
Also, I am fairly certain that the Deepmind approach, using neural nets that learn from pixel data will not suffice. After all, not even us humans, equipped with a pre-tuned specialized brain, learn a new game just by looking at it. Instead, we immediately interpret what we see and apply known rules to it to deduce new facts. By the way: one of the shortcuts mentioned earlier is the fact that we excel at visual pattern recognition. To the point, we even recognize patters where there aren’t any (in clouds or peanuts or random wood that “looks exactly like the face of Jesus”).
Let’s take famous Super Mario as an example. From a few pixels on the screen we immediately recognize it is supposed to depict a human being. It has legs, so it can walk. When Mario walks all the other pixels move right to left. This means Mario is moving left to right and the camera changes with him. It will require dedicated action to make him jump, but he will get down by himself due to gravity. Other characters are likely to be enemies if they frown or throw stuff at us, but friends if they smile. All of this knowledge that we are born with or have acquired outside the game help us mastering the game faster. Because we don’t reason over the raw data (pixels) but over our interpretation of the raw data (Mario).
Bots can’t do that. They are unable to interpret a syntax semantically and attach a meaning to their input. But what if we gave them some support to at least take the first steps in this direction?
Section 2: How to think like a human: mapping cognitive abilities
This brings us back to the initial “silly questions”.
- What choke on the map should I protect with my units before I expand to my natural? What’s a choke anyways?
There are algorithms able to define what a choke is. And they have been shown to produce classifications similar to the ones done by humans (see BWTA and this paper)
But what is lacking is an interpretation. Apart from the idea of coupling a physics engine to a neural net, which in a way couples experience to learning ability, further progress can be achieved by adding dedicated components corresponding to the cognitive abilities:
Attentional control: the decision making involved in deciding what information streams to pay attention to, whether to process them and how to process them. Thread scheduling.
Example: We may decide to ignore the audio channel in our bot. Or we may use a classic tree-based search and need to decide what branches to prune and what branches to calculate in more depth = pay more attention to.
Working memory: the system responsible for holding, processing, and manipulating information. This definition for humans can be applied 1:1 to bots. It includes not only how much memory is available, but also the structure of it. The structure determines how fast memory read and write operations are and makes a trade-off between speed and size.
Examples: use a linked list of all units encountered in the game (fast delete, O(n) search). Cache pre-calculated income curve calculations. Load a heat map into memory consisting of condensed snapshots from every 10 second interval of all past games the bot has played.
Reasoning: a database containing facts and rules, as well as the ability to draw conclusions. The Prolog programming language provides a direct implementation of this ability.
Example: Facts about unit stats and rules how they interact allows reasoning as to how to counter a specific enemy army composition.
Problem solving: Probably best mapped to computational pattern recognition. Very generally spoken it is the ability to detect pattern on an adequate level of abstraction such that solutions from known problems can be applied. Pattern recognition covers an entire branch of machine learning.
Example: abstract the scenario of blocking a ramp with SCVs to prevent a Zergling rush to blocking any kind of melee unit with any other unit. This ability can then potentially be applied in unforeseen situations.
Planning: the computational power to explore search trees and known relations to simulate future outcomes and then pick one outcome that satisfies the goal to achieve.
Example: A combat simulator or an algorithm to plan the safest route for a dropship.
Conclusion
Only when everything comes together can we reason: “my main is surrounded by non-walkable terrain, except for one exit. (attentional control) At this point, my opponent cannot have any flying units yet (Reasoning, working memory). Therefore, if he wants to attack any of my buildings or workers, he must move through the single choke (problem solving). I can block enemy units with my own units (working memory). On the entire path from his base to my base, the choke is the point where least units are required to fully block his path (problem solving). The earliest rush I have experienced so far arrived at the x minute mark (working memory). But this time we are cross-position, so I will adjust a bit and make sure I block my choke at the y minute mark. (planning)” etc.
How to glue all of this together?
I don't know. But I'm sure we will find out
), and of course neural nets, which are great at iteratively optimizing a utility function, simulating learning. But yes, combining different approaches to form a whole is a real challenge.
