In this chapter, we begin to look at how we identify problems that AI would like to solve. The process behind this: knowledge engineering, is not only a really important step when building AI solutions, but also an entire sub-discipline of AI in itself! This often is focussed on looking at a range of potential problems, referred to as a domain and looking at what factors are common or important. We start by focusing on the key definitions required when representing the world and associate these with examples from games to help ease your understanding.
The Importance of Determinism
Determinism is the ability to predict future outcome, given we know what a particular object is going to do. If we consider an object or system to be deterministic it means that, provided we have studied that system sufficiently, we can predict what it will do next. Conversely, there are non-deterministic systems: which due to their nature, are not predictable. Naturally, a system whose future actions we cannot predict is a lot harder to deal with that one which is predictable.
When playing video games, often large scales bosses, such as Ganondorf in the Legend of Zelda, are deterministic systems. Bosses often exhibit strict patterns of behaviour that eventually lead to an opening for attack. Provided a player learns that pattern, they can begin to eliminate said boss with ease.
Meanwhile, games such as Ms. Pac-Man are an example of non-determinisim. While each ghost has a strategy they follow, they can mix things up at certain points. Should a ghost reach a decision point in the map, they can either follow their strategy or make a completely random move. This means we can never really predict what they’re going to do! Making the game a lot harder than the original.
SIDE NOTE: In fact, non-deterministic ghosts is what makes Ms. Pac-Man so interesting for AI researchers. If you’re interested, check out ‘What’s The Deal With Pac-Man?’, where we detail over 10 years of AI research in playing Pac-Man.
How Much Information Do We Have?
As we move into Part 6, we will begin to look at how the information of the world helps us understand ‘where’ we are. Naturally, we would like to have as much knowledge as possible, so that our agent can conduct his rational decision making. If we know everything about the problem we are trying to solve, we can say that this domain exhibits perfect information, since we can see everything that is happening and use that to our advantage.
Board games such as Chess or even video games like FIFA, are a great example of perfect information. In either case, while we do not know what the opposing player is going to do, we can see what their options are and from that make our own judgements. This is why playing Chess takes so long, given that each player can see each others pieces and predict what each other will do for several moves ahead. FIFA is remarkably similar, since we can see all the players on the screen and we know where the ball is. We can then make smart decisions to push ahead and score a goal.
Conversely, domains that do not tell us everything we would like to know are referred to as having imperfect information. This appears frequently with card games such as Blackjack and Texas Hold’em: where the player only really knows what cards they are carrying. They can make educated guesses as to what other players/the dealer are holding, but that’s all they are: guesses. Meanwhile, Real Time Strategy (RTS) games are interesting, given that they typically start as imperfect information problems due to the ‘fog of war’. However, as the player explores the world, this problem exhibits perfect information given that the fog has been clear.
What Else Is Going On?
Of course when our AI is attempting to make a decision, we always have to pay attention to what is happening around us, if at all. Typically if we are playing board games, we can say that the domain is static, since while we are making our (rational) decisions, nothing else is happening that will impact what we are doing. Meanwhile, games such as Call of Duty are the opposite, given that if you are standing in the middle of an environment, other characters (whether they’re NPCs in the campaign, or human players online) are constantly changing the world around us: shots are fired, grenades are thrown etc. In other words, the world is dynamic. This forces us to pay attention to what is happening right now while making decisions. This can potentially change the final decision given that we need to react to nearby change.
Breaking It Down Frame By Frame
One issue that is often faced by AI researchers is whether we can break the world down into chunks: so we can look at the world at a given point in time and then use those chunks as the basis of our knowledge framework. This suggests that the world is discrete, given we can take a snapshot of the world and think about what to do in that snapshot. However, in many dynamic situations, we often faced with continuous domains that rely on us managing our knowledge to compensate for the passage of time. This is a common problem in the real world when dealing with safety critical systems.
Despite this distinction, it is often possible to break problems down into discrete models. Video games are a great example of this. A video game is, by its definition, discrete. This is because a video game is broken down into a number of frames of execution per second. This is the update logic of a video game that updates what is happening. While some games vary in their frame rate (typically from 30 to 60 fps) at the end of the day these are discrete models of the problem domain that can be looked at a certain number of times a second.
How Many Agents Are There?
When building our representation of the world, we also need to factor whether there are actually other agents floating around. Why is that important? Well, these other agents can potentially change the world just like our agent can. In fact they could make changes we can’t achieve! This complicates matters and we may need to be aware of their impact in multi-agent domains. Meanwhile, characters like the Goomba, who we mentioned in Part 4, don’t need to be considered given that they’re not agents. So in some circumstances we don’t need to consider anyone else, given it is a single-agent domain.
A Lot of Terminology
So far we’ve covered a lot of terms that define how we look at the world. These are very useful for AI people, given that it helps identify not only how difficult the problem can be, but also what methods they can use to solve it. As I hope is clear from earlier, certain traits make a problem a lot more complicated. Games that imperfect information and non-determinism (i.e. I don’t know exactly what’s going on and I can’t be sure of what will happen next) are going to be rather tricky to get around. However, that does not mean a game that has perfect information and is deterministic is going to be any easy. A prime candidate for that is:
Chess! We always know the state of the board in Chess and know what potential moves can arise. While we can’t say with 100% certainty what our opponents action will be, we know what it can be and we may be able to predict which action they choose. It’s this breadth of selection that continues to make Chess a challenging AI problem. As we move into Part 6, we will begin to address why that is the case.
Some More Homework
That’s a lot of information to sink in from both Part 4 and Part 5. So in the meantime, here’s some more homework. Look back on that game you played originally. Think about what you see now when you play it:
- Are the enemy characters agents? Or simply dynamic objects with some scripted movement?
- Have a look at the first of our tutorials held on this site: AI DIY #1. In this tutorial you are tasked with taking a game and figuring out how the topics discussed in Part 5 affect it. Try using the game you played as part of the Introduction.
And lastly, in preparation for Part 6:
- What are the important pieces of information that define what I am doing in each frame of the game?
This last part is important, given we always need to know where we are and what is happening in the world. This is the focus of Part 6 when we begin to discuss states.
Chapter 2, Section 3 of (Russell, S. and Norvig, P., 2009) – Artificial Intelligence: A Modern Approach, Prentice Hall.