Overview
In this chapter, you will be introduced to the fundamentals of Artificial Intelligence (AI), which are the foundations of various fields of AI. You will also come across different algorithms, including MinMax and A*, through simple coding exercises using the Python programming language. You will also be implementing your first AI through a simple tic-tac-toe game where you will be teaching the program how to win against a human player. By the end of this chapter, you will learn how to use popular Python libraries to develop intelligent AI-driven programs.
Introduction
Before discussing the different AI techniques and algorithms, we will look at the fundamentals of AI and machine learning and go through a few basic definitions. Real-world examples will be used to present the basic concepts of AI in an easy-to-digest way.
AI attempts to replicate human intelligence using hardware and software solutions. It is based on reverse engineering. For example, artificial neural networks are modeled after the way the human brain works. Beyond neural networks, there are many other models in neuroscience that can be used to solve real-world problems using AI. Companies that are known to be using AI in their fields include Google, with Google Translate, Apple, with Face ID, Amazon, with its Alexa products, and even Uber and Tesla, who are still working on building self-driving cars.
On the other hand, machine learning is a term that is often confused with AI. It originates from the 1950s and was first defined by Arthur Lee Samuel in 1959.
In his book called Machine Learning, Tom Mitchell proposed a simple definition of it: "The field of machine learning is concerned with the question of how to construct computer programs that automatically improve with experience."
We can understand this as machine learning being the field where the goal is to build a computer program capable of learning patterns from data and improve its learning ability with more data.
He also proposed a more formal definition, which is that a computer program is said to learn from experience, E, with respect to a task, T, and a performance measure, P, if its performance on T, as measured by P, improves with experience, E. This can be translated as what a computer program requires in order for it to be learning. We can see E (the experience) as the data that needs to be fed to the machine, T, as the type of decision that the machine needs to perform, and P as the measure of its performance.
From these two definitions, we can conclude that machine learning is one way to achieve AI. However, you can have AI without machine learning. For instance, if you hardcode rules and decision trees, or you apply search techniques, you can create an AI agent, even though your approach has little to do with machine learning.
AI and machine learning have helped the scientific community harness the explosion of big data with more and more data being created every second. With AI and machine learning, scientists can extract information that human eyes cannot process fast enough on these huge datasets.
Now that we have been introduced to AI and machine learning, let's focus on AI.
How Does AI Solve Problems?
AI automates human intelligence based on the way a human brain processes information.
Whenever we solve a problem or interact with people, we go through a process. By doing this, we limit the scope of a problem or interaction. This process can often be modeled and automated in AI.
AI makes computers appear to think like humans.
Sometimes, it feels like the AI knows what we need. Just think about the personalized coupons you receive after shopping online. AI knows which product we will most likely be purchasing. Machines are able to learn your preferences through the implementation of different techniques and models, which we will look at later in this book.
AI is performed by computers that are executing low-level instructions.
Even though a solution may appear to be intelligent, we write code, just like with any other software solution in AI. Even if we are simulating neurons, simple machine code and computer hardware executes the thinking process.
Most AI applications have one primary objective. When we interact with an AI application, it seems human-like because it can restrict a problem domain to a primary objective. Therefore, the process whereby the AI reaches the objective can be broken down into smaller and simpler low-level instructions.
AI may stimulate human senses and thinking processes for specialized fields.
You must be able to simulate human senses and thoughts, and sometimes trick AI into believing that we are interacting with another human. In some special cases, we can even enhance our own senses.
Similarly, when we interact with a chatbot, for instance, we expect the bot to understand us. We expect the chatbot or even a voice recognition system to provide a computer-human interface that fulfills our expectations. In order to meet these expectations, computers need to emulate human thought processes.
Diversity of Disciplines in AI
A self-driving car that cannot sense other cars driving on the same highway would be incredibly dangerous. The AI agent needs to process and sense what is around it in order to drive the car. However, this is not enough since, without understanding the physics of moving objects, driving the car in a normal environment would be an almost impossible, not to mention deadly, task.
In order to create a usable AI solution, different disciplines are involved, such as the following:
- Robotics: To move objects in space
- Algorithm theory: To construct efficient algorithms
- Statistics: To derive useful results, predict the future, and analyze the past
- Psychology: To model how the human brain works
- Software engineering: To create maintainable solutions that endure the test of time
- Computer science or computer programming: To implement our software solutions in practice
- Mathematics: To perform complex mathematical operations
- Control theory: To create feed-forward and feedback systems
- Information theory: To represent, encode, decode, and compress information
- Graph theory: To model and optimize different points in space and to represent hierarchies
- Physics: To model the real world
- Computer graphics and image processing: To display and process images and movies
In this book, we will cover a few of these disciplines, including algorithm theory, statistics, computer science, mathematics, and image processing.
Fields and Applications of AI
Now that we have been introduced to AI, let's move on and see its application in real life.
Simulation of Human Behavior
Humans have five basic senses that can be divided into visual (seeing), auditory (listening), kinesthetic (moving), olfactory (smelling), and gustatory (tasting). However, for the purposes of understanding how to create intelligent machines, we can separate these disciplines as follows:
- Listening and speaking
- Understanding language
- Remembering things
- Thinking
- Seeing
- Moving
A few of these are out of scope for us because the purpose of this chapter is to understand the fundamentals. In order to move a robot arm, for instance, we would have to study complex university-level math to understand what's going on, but we will only be sticking to the practical aspects in this book:
- Listening and speaking: Using a speech recognition system, AI can collect information from a user. Using speech synthesis, it can turn internal data into understandable sounds. Speech recognition and speech synthesis techniques deal with the recognition and construction of human sounds that are emitted or that humans can understand.
For instance, imagine you are on a trip to a country where you don't speak the local language. You can speak into the microphone of your phone, expect it to understand what you say, and then translate it into the other language. The same can happen in reverse with the locals speaking and AI translating the sounds into a language you understand. Speech recognition and speech synthesis make this possible.
Note
An example of speech synthesis is Google Translate. You can navigate to https://translate.google.com/ and make the translator speak words in a non-English language by clicking the loudspeaker button below the translated word.
- Understanding language: We can understand natural language by processing it. This field is called natural language processing, or NLP.
When it comes to NLP, we tend to learn languages based on statistical learning by learning the statistical relationship between syllables.
- Remembering things: We need to represent things we know about the world. This is where creating knowledge bases and hierarchical representations called ontologies comes into play. Ontologies categorize things and ideas in our world and contain relations between these categories.
- Thinking: Our AI system has to be an expert in a certain domain by using an expert system. An expert system can be based on mathematical logic in a deterministic way, as well as in a fuzzy, non-deterministic way.
The knowledge base of an expert system is represented using different techniques. As the problem domain grows, we create hierarchical ontologies.
We can replicate this structure by modeling the network on the building blocks of the brain. These building blocks are called neurons, and the network itself is called a neural network.
- Seeing: We have to interact with the real world through our senses. We have only touched upon auditory senses so far, in regard to speech recognition and synthesis. What if we had to see things? If that was the case, we would have to create computer vision techniques to learn about our environment. After all, recognizing faces is useful, and most humans are experts at that.
Computer vision depends on image processing. Although image processing is not directly an AI discipline, it is a required discipline for AI.
- Moving: Moving and touching are natural to us humans, but they are very complex tasks for computers. Moving is handled by robotics. This is a very math-heavy topic.
Robotics is based on control theory, where you create a feedback loop and control the movement of your object based on the feedback gathered. Control theory has applications in other fields that have absolutely nothing to do with moving objects in space. This is because the feedback loops that are required are similar to those modeled in economics.
Simulating Intelligence – the Turing Test
Alan Turing, inventor of the Turing machine, an abstract concept that's used in algorithm theory, suggested a way to test intelligence. This test is referred to as the Turing test in AI literature.
Using a text interface, an interrogator chats to a human and a chatbot. The job of the chatbot is to mislead the interrogator to the extent that they cannot tell whether the computer is human.
What Disciplines Do We Need to Pass the Turing Test?
First, we need to understand a spoken language to know what the interrogator is saying. We do this by using Natural Language Processing (NLP). We also must respond to the interrogator in a credible way by learning from previous questions and answers using AI models.
We need to be an expert of things that the human mind tends to be interested in. We need to build an expert system of humanity, involving the taxonomy of objects and abstract thoughts in our world, as well as historical events and even emotions.
Passing the Turing test is very hard. Current predictions suggest we won't be able to create a system good enough to pass the Turing test until the late 2020s. Pushing this even further, if this is not enough, we can advance to the Total Turing Test, which also includes movement and vision.
Next, we will move on and look at the tools and learning models in AI.
AI Tools and Learning Models
In the previous sections, we discovered the fundamentals of AI. One of the core tasks of AI is learning. This is where intelligent agents come into the picture.
Intelligent Agents
When solving AI problems, we create an actor in the environment that can gather data from its surroundings and influence its surroundings. This actor is called an intelligent agent.
An intelligent agent is as follows:
- Is autonomous
- Observes its surroundings through sensors
- Acts in its environment using actuators (which are the components that are responsible for moving and controlling a mechanism)
- Directs its activities toward achieving goals
Agents may also learn and have access to a knowledge base.
We can think of an agent as a function that maps perceptions to actions. If the agent has an internal knowledge base, then perceptions, actions, and reactions may alter the knowledge base as well.
Actions may be rewarded or punished. Setting up a correct goal and implementing a carrot and stick situation helps the agent learn. If goals are set up correctly, agents have a chance of beating the often more complex human brain. This is because the primary goal of the human brain is survival, regardless of the game we are playing. An agent's primary motive is reaching the goal itself. Therefore, intelligent agents do not get embarrassed when making a random move without any knowledge.
The Role of Python in AI
In order to put basic AI concepts into practice, we need a programming language that supports AI. In this book, we have chosen Python. There are a few reasons why Python is such a good choice for AI:
- Convenience and Compatibility: Python is a high-level programming language. This means that you don't have to worry about memory allocation, pointers, or machine code in general. You can write code in a convenient fashion and rely on Python's robustness. Python is also cross-platform compatible.
- Popularity: The strong emphasis on developer experience makes Python a very popular choice among software developers. In fact, according to a 2018 developer survey by https://www.hackerrank.com, across all ages, Python ranks as the number one preferred language of software developers. This is because Python is easily readable and simple. Therefore, Python is great for rapid application development.
- Efficiency: Despite being an interpreted language, Python is comparable to other languages that are used in data science, such as R. Its main advantage is memory efficiency, since Python can handle large, in-memory databases.
Note
Python is a multi-purpose language. It can be used to create desktop applications, database applications, mobile applications, and games. The network programming features of Python are also worth mentioning. Furthermore, Python is an excellent prototyping tool.
Why Is Python Dominant in Machine Learning, Data Science, and AI?
To understand the dominant nature of Python in machine learning, data science, and AI, we have to compare Python to other languages that are also used in these fields.
Compared to R, which is a programming language built for statisticians, Python is much more versatile and easy as it allows programmers to build a diverse range of applications, from games to AI applications.
Compared to Java and C++, writing programs in Python is significantly faster. Python also provides a high degree of flexibility.
There are some languages that are similar in nature when it comes to flexibility and convenience: Ruby and JavaScript. Python has an advantage over these languages because of the AI ecosystem that's available for Python. In any field, open source, third-party library support vastly determines the success of that language. Python's third-party AI library support is excellent.
Anaconda in Python
We installed Anaconda in the Preface. Anaconda will be our number one tool when it comes to experimenting with AI.
Anaconda comes with packages, IDEs, data visualization libraries, and high-performance tools for parallel computing in one place. Anaconda hides configuration problems and the complexity of maintaining a stack for data science, machine learning, and AI. This feature is especially useful in Windows, where version mismatches and configuration problems tend to arise the most.
Anaconda comes with Jupyter Notebook, where you can write code and comments in a documentation style. When you experiment with AI features, the flow of your ideas resembles an interactive tutorial where you run each step of your code.
Note
IDE stands for Integrated Development Environment. While a text editor provides some functionalities to highlight and format code, an IDE goes beyond the features of text editors by providing tools to automatically refactor, test, debug, package, run, and deploy code.
Python Libraries for AI
The list of libraries presented here is not complete as there are more than 700 available in Anaconda. However, these specific ones will get you off to a good start because they will give you a good foundation to be able to implement the fundamental AI algorithms in Python:
- NumPy: NumPy is a computing library for Python. As Python does not come with a built-in array data structure, we have to use a library to model vectors and matrices efficiently. In data science, we need these data structures to perform simple mathematical operations. We will use NumPy extensively in future chapters.
- SciPy: SciPy is an advanced library containing algorithms that are used for data science. It is a great complementary library to NumPy because it gives you all the advanced algorithms you need, whether it be a linear algebra algorithm, image processing tool, or a matrix operation.
- pandas: pandas provides fast, flexible, and expressive data structures, such as one-dimensional series and two-dimensional DataFrames. It efficiently loads, formats, and handles complex tables of different types.
- scikit-learn: scikit-learn is Python's main machine learning library. It is based on the NumPy and SciPy libraries. scikit-learn provides you with the functionality required to perform both classification and regression, data preprocessing, as well as supervised and unsupervised learning.
- NLTK: We will not deal with NLP in this book, but NLTK is still worth mentioning because this library is the main natural language toolkit of Python. You can perform classification, tokenization, stemming, tagging, parsing, semantic reasoning, and many other operations using this library.
- TensorFlow: TensorFlow is Google's neural network library, and it is perfect for implementing deep learning AI. The flexible core of TensorFlow can be used to solve a vast variety of numerical computation problems. Some real-world applications of TensorFlow include Google voice recognition and object identification.
A Brief Introduction to the NumPy Library
The NumPy library will play a major role in this book, so it is worth exploring it further.
After launching your Jupyter Notebook, you can simply import numpy as follows:
import numpy as np
Once numpy has been imported, you can access it using its alias, np. NumPy contains the efficient implementation of some data structures, such as vectors and matrices.
Let's see how we can define vectors and matrices:
np.array([1,3,5,7])
The expected output is this:
array([1, 3, 5, 7])
We can declare a matrix using the following syntax:
A = np.mat([[1,2],[3,3]])
A
The expected output is this:
matrix([[1, 2],
[3, 3]])
The array method creates an array data structure, while .mat creates a matrix.
We can perform many operations with matrices. These include addition, subtraction, and multiplication. Let's have a look at these operations here:
Addition in matrices:
A + A
The expected output is this:
matrix([[2, 4],
[6, 6]])
Subtraction in matrices:
A - A
The expected output is this:
matrix([[0, 0],
[0, 0]])
Multiplication in matrices:
A * A
The expected output is this:
matrix([[ 7, 8],
[12, 15]])
Matrix addition and subtraction work cell by cell.
Matrix multiplication works according to linear algebra rules. To calculate matrix multiplication manually, you have to align the two matrices, as follows:
Figure 1.1: Multiplication calculation with two matrices
To get the (i,j)th element of the matrix, you compute the dot (scalar) product on the ith row of the matrix with the jth column. The scalar product of two vectors is the sum of the product of their corresponding coordinates.
Another frequent matrix operation is the determinant of the matrix. The determinant is a number associated with square matrices. Calculating the determinant using NumPy's linalg function (linear algebra algorithms) can be seen in the following line of code:
np.linalg.det( A )
The expected output is this:
-3.0000000000000004
Technically, the determinant can be calculated as 1*3 – 2*3 = -3. Notice that NumPy calculates the determinant using floating-point arithmetic, so the accuracy of the result is not perfect. The error is due to the way floating points are represented in most programming languages.
We can also transpose a matrix, as shown in the following line of code:
np.matrix.transpose(A)
The expected output is this:
matrix([[1, 3],
[2, 3]])
When calculating the transpose of a matrix, we flip its values over its main diagonal.
NumPy has many other important features, so we will use it in most of the chapters in this book.
Exercise 1.01: Matrix Operations Using NumPy
We will be using Jupyter Notebook and the following matrix to solve this exercise.
We will calculate the square of the matrix, which is determinant of the matrix and the transpose of the matrix shown in the following figure, using NumPy:
Figure 1.2: A simple matrix representation
The following steps will help you to complete this exercise:
- Open a new Jupyter Notebook file.
- Import the numpy library as np:
import numpy as np
- Create a two-dimensional array called A for storing the [[1,2,3],[4,5,6],[7,8,9]] matrix using np.mat:
A = np.mat([[1,2,3],[4,5,6],[7,8,9]])
A
The expected output is this:
matrix([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
Note
If you have created an np.array instead of np.mat, the solution for the array multiplication will be incorrect.
- Next, we perform matrix multiplication using the asterisk and save the result in a variable called matmult, as shown in the following code snippet:
matmult = A * A
matmult
The expected output is this:
matrix([[ 30, 36, 42],
[ 66, 81, 96],
[102, 126, 150]])
- Next, manually calculate the square of A by performing matrix multiplication. For instance, the top-left element of the matrix is calculated as follows:
1 * 1 + 2 * 4 + 3 * 7
The expected output is this:
30
- Use np.linalg.det to calculate the determinant of the matrix and save the result in a variable called det:
det = np.linalg.det( A )
det
The expected output (might vary slightly) is this:
0.0
- Use np.matrix.transpose to get the transpose of the matrix and save the result in a variable called transpose:
transpose = np.matrix.transpose(A)
transpose
The expected output is this:
matrix([[1, 4, 7],
[2, 5, 8],
[3, 6, 9]])
If T is the transpose of matrix A, then T[j][i] is equal to A[i][j].
Note
To access the source code for this specific section, please refer to https://packt.live/316Vd6Z.
You can also run this example online at https://packt.live/2BrogHL. You must execute the entire Notebook in order to get the desired result.
By completing this exercise, you have seen that NumPy comes with many useful features for vectors, matrices, and other mathematical structures.
In the upcoming section, we will be implementing AI in an interesting tic-tac-toe game using Python.
Python for Game AI
An AI game player is nothing but an intelligent agent with a clear goal: to win the game and defeat all the other players. AI experiments have achieved surprising results when it comes to games. Today, no human can defeat an AI in the game of chess.
The game Go was the last game where human players could consistently defeat a computer player. However, in 2017, Google's game-playing AI called AlphaGo defeated the world number 1 ranked Go player.
Intelligent Agents in Games
An intelligent agent plays according to the rules of the game. The agent can sense the current state of the game through its sensors and can evaluate the potential steps. Once the agent finds the best possible step, it performs the action using its actuators. The agent finds the best possible action to reach the goal based on the information it has. Actions are either rewarded or punished. The carrot and stick are excellent examples of rewards and punishment. Imagine a donkey in front of your cart. You put a carrot in front of the eyes of the donkey, so the animal starts walking toward it. As soon as the donkey stops, the rider may apply punishment with a stick. This is not a human way of moving, but rewards and punishment control living organisms to some extent. The same happens to humans at school, at work, and in everyday life as well. Instead of carrots and sticks, we have income and legal punishment to shape our behavior.
In most games, a good sequence of actions results in a reward. When a human player feels rewarded, that makes the human feel happy. Humans tend to act in a way that maximizes their happiness. Intelligent agents, on the other hand, are only interested in their goal, which is to maximize their reward and minimize the punishment that's affecting their performance score.
When modeling games, we must determine their state space. An action causes a state transition. When we explore the consequences of all possible actions, we get a decision tree. This tree goes deeper as we start exploring the possible future actions of all players until the game ends.
The strength of AI is the execution of millions of possible steps each second. Therefore, game AI often boils down to a search exercise. When exploring all of the possible sequences of moves in a game, we get the state tree of a game.
Consider a chess AI. What is the problem with evaluating all possible moves by building a state tree consisting of all of the possible sequences of moves?
Chess is an EXPTIME game complexity-wise. The number of possible moves explodes combinatorically.
White starts with 20 possible moves: the eight pawns may move either one or two steps, and the two knights may move either up-up-left, or up-up-right. Then, black can make any of these 20 moves. There are already 20*20 = 400 possible combinations after just one move per player.
After the second move, we get 8,902 possible board constellations, and this number just keeps on growing. Just take seven moves, and you have to search through 10,921,506 possible constellations.
The average length of a chess game is approximately 40 moves. Some exceptional games take more than 200 moves to finish.
As a consequence, the computer player simply does not have time to explore the whole state space. Therefore, the search activity has to be guided with proper rewards, punishment, and simplifications of the rules.
Breadth First Search and Depth First Search
Creating a game AI is often a search exercise. Therefore, we need to be familiar with the two primary search techniques:
- Breadth First Search (BFS)
- Depth First Search (DFS)
These search techniques are applied on a directed rooted tree.
A tree is a data structure that has nodes, and edges connecting these nodes in such a way that any two nodes of the tree are connected by exactly one path. Have a look at the following figure:
Figure 1.3: A directed rooted tree
When the tree is rooted, there is a special node in the tree called the root, which is where we begin our traversal. A directed tree is a tree where the edges may only be traversed in one direction. Nodes may be internal nodes or leaves. Internal nodes have at least one edge, through which we can leave the node. A leaf has no edges pointing out from the node.
In AI search, the root of the tree is the starting state. We traverse from this state by generating the successor nodes of the search tree. Search techniques differ, depending on the order in which we visit these successor nodes.
Breadth First Search (BFS)
BFS is a search technique that, starting from the root node (node 1), will start exploring the closest node on the same depth (or level) before moving to the next depth:
Figure 1.4: A BFS tree
In the preceding figure, you can see the search order of the BFS technique. Starting from the root node (1), BFS will go to the next level and explore the closest node (2) before looking at the other nodes on the same level (3 and 4). Then, it will move to the next level and explore 5 and 6 as they are close to each other before going back through to node 3, finishing on the last node (7), and so on.
Depth First Search (DFS)
DFS is a search technique that, starting from the root node (node 1), will start exploring the same branch as much as possible before moving to the next closest branch:
Figure 1.5: A DFS tree
In the preceding figure, you can see the search order of the DFS technique. Starting from the root node (1), DFS will go to the closest node (2) and explore all the way to the end of the branch (3) on the third depth before going back to the node (2) and finish by exploring its second branch (4). Then, it will move back to the second depth and start the same process with the next branch (6) before finishing with the last branch (7).
Now, suppose we have a tree defined by its root and a function that generates all the successor nodes from the root. In the following example, each node has a value and a depth. We start from 1 and may either increase the value by 1 or 2. Our goal is to reach the value 5:
Note
The code snippet shown here uses a backslash ( ) to split the logic across multiple lines. When the code is executed, Python will ignore the backslash, and treat the code on the next line as a direct continuation of the current line.
root = {'value': 1, 'depth': 1}
def succ(node):
if node['value'] == 5:
return []
elif node['value'] == 4:
return [{'value': 5,'depth': node['depth']+1}]
else:
return [{'value': node['value']+1,
'depth':node['depth']+1},
{'value': node['value']+2,
'depth':node['depth']+1}]
In the preceding code snippet, we have initialized the root node as having a value and depth of 1. Then, we created a function called succ that takes a node as input. This function will have 3 different cases:
- If the input node value is 5, then return nothing as we will have already reached our goal (5).
- If the input node value is 4, then return the value 5 and add 1 to the current depth.
- If the value is anything else, then add 1 to the depth and create two cases for the value, +1 and +2.
First, we will perform BFS, as shown here:
def bfs_tree(node):
nodes_to_visit = [node]
visited_nodes = []
while len(nodes_to_visit) > 0:
current_node = nodes_to_visit.pop(0)
visited_nodes.append(current_node)
nodes_to_visit.extend(succ(current_node))
return visited_nodes
bfs_tree(root)
In the preceding code snippet, we have implemented the bfs_tree function by taking a node as input. This function can be broken down into three parts:
The first part is initializing the nodes_to_visit and visited_nodes variables.
The second part is where BFS is implemented:
- The current_node variable takes away the first element of the nodes_to_visit variable.
- The visited_nodes variable adds this element to its list.
- The nodes_to_visit variable adds the newly generated nodes from the call of succ with the current_node as input to it.
The preceding three instructions are wrapped into a loop defined by the number of elements inside the nodes_to_visit variable. As long as nodes_to_visit has at least one element, then the loop will keep going.
The third part, which is the end of the function, will return the entire list of values from the visited_nodes variable.
The expected output is this:
[{'value': 1, 'depth': 1},
{'value': 2, 'depth': 2},
{'value': 3, 'depth': 2},
{'value': 3, 'depth': 3},
{'value': 4, 'depth': 3},
{'value': 4, 'depth': 3},
{'value': 5, 'depth': 3},
{'value': 4, 'depth': 4},
{'value': 5, 'depth': 4},
{'value': 5, 'depth': 4},
{'value': 5, 'depth': 4},
{'value': 5, 'depth': 5}]
As you can see, BFS is searching through the values of the same depth before moving to the next level of depth and exploring the values of it. Notice how depth and value are increasing in sequence. This will not be the case in DFS.
If we had to traverse a graph instead of a directed rooted tree, BFS would look different: whenever we visit a node, we would have to check whether the node had been visited before. If the node had been visited before, we would simply ignore it.
In this chapter, we will only use Breadth First Traversal on trees. DFS is surprisingly similar to BFS. The difference between DFS and BFS is the sequence in which you access the nodes. While BFS visits all the children of a node before visiting any other nodes, DFS digs deep into the tree.
Have a look at the following example, where we're implementing DFS:
def dfs_tree(node):
nodes_to_visit = [node]
visited_nodes = []
while len(nodes_to_visit) > 0:
current_node = nodes_to_visit.pop()
visited_nodes.append(current_node)
nodes_to_visit.extend(succ(current_node))
return visited_nodes
dfs_tree(root)
In the preceding code snippet, we have implemented the dfs_tree function by taking a node as input. This function can be broken down into three parts:
The first part is initializing the nodes_to_visit and visited_nodes variables.
The second part is where DFS is implemented:
- The current_node variable takes away the last element of the nodes_to_visit variable.
- The visited_nodes variable adds this element to its list.
- The nodes_to_visit variable adds the newly generated nodes from the call of succ with current_node as input to it.
The preceding three instructions are wrapped into a loop defined by the number of elements inside the nodes_to_visit variable. As long as nodes_to_visit has at least one element, then the loop will keep going.
At the end, that is at the third part, the function will return the entire list of values from visited_nodes.
As you can see, the main difference between BFS and DFS is the order in which we took an element out of nodes_to_visit. For BFS, we take the first element, whereas for DFS, we take the last one.
The expected output is this:
[{'value': 1, 'depth': 1},
{'value': 3, 'depth': 2},
{'value': 5, 'depth': 3},
{'value': 4, 'depth': 3},
{'value': 5, 'depth': 4},
{'value': 2, 'depth': 2},
{'value': 4, 'depth': 3},
{'value': 5, 'depth': 4},
{'value': 3, 'depth': 3},
{'value': 5, 'depth': 4},
{'value': 4, 'depth': 4},
{'value': 5, 'depth': 5}]
Notice how the DFS algorithm digs deep fast (the depth reaches higher values faster than BFS). It does not necessarily find the shortest path first, but it is guaranteed to find a leaf before exploring a second path.
In game AI, the BFS algorithm is often better for the evaluation of game states because DFS may get lost. Imagine starting a chess game, where a DFS algorithm may easily get lost in exploring the options for a move.
Exploring the State Space of a Game
Let's explore the state space of a simple game: tic-tac-toe. A state space is the set of all possible configurations of a game, which, in this case, means all the possible moves.
In tic-tac-toe, a 3x3 game board is given. Two players play this game. One plays with the sign X, while the other plays with the sign O. X starts the game, and each player makes a move after the other. The goal of the game is to get three of your own signs horizontally, vertically, or diagonally.
Let's denote the cells of the tic-tac-toe board, as follows:
Figure 1.6: Tic-tac-toe board
In the following example, X started at position 1. O retaliated at position 5, X made a move at position 9, and then O moved to position 3:
Figure 1.7: Tic-tac-toe board with noughts and crosses
This was a mistake by the second player, because now X is forced to place a sign on cell 7, creating two future scenarios for winning the game. It does not matter whether O defends by moving to cell 4 or 8 – X will win the game by selecting the other unoccupied cell.
Note
You can try out the game at http://www.half-real.net/tictactoe/.
For simplicity, we will only explore the state space belonging to the cases when the AI player starts. We will start with an AI player who plays randomly, placing a sign in an empty cell. After playing with this AI player, we will create a complete decision tree. Once we generate all possible game states, you will experience their combinatorial explosion. As our goal is to make these complexities simple, we will use several different techniques to make the AI player smarter and reduce the size of the decision tree.
By the end of this experiment, we will have a decision tree that has fewer than 200 different game endings and, as a bonus, the AI player will never lose a single game.
To make a random move, you will have to know how to choose a random element from a list using Python. We will use the choice function of the random library to do so:
from random import choice
choice([2, 4, 6, 8])
This time, the output is 6, but for you, it can be any number from the list.
The output of the choice function is a random element of the list.
Note
We will use the factorial notation in the following section. A factorial is denoted by the "!" exclamation mark. By definition, 0! = 1, and n! = n*(n-1)!. In our example, 9! = 9* 8! = 9*8*7! = … = 9*8*7*6*5*4*3*2*1.
Estimating the Number of Possible States in a Tic-Tac-Toe Game
Make a rough estimate of the number of possible states on each level of the state space of the tic-tac-toe game:
- In our estimation, we will not stop until all of the cells of the board have been filled. A player might win before the game ends, but for the sake of uniformity, we will continue the game.
- The first player will choose one of the nine cells. The second player will choose one out of the eight remaining cells. The first player can then choose one out of the seven remaining cells. This goes on until either player wins the game, or the first player is forced to make the ninth and last move.
- The number of possible decision sequences is, therefore, 9! = 362,880. A few of these sequences are invalid because a player may win the game in fewer than nine moves. It takes at least five moves to win a game because the first player needs to move three times.
- To calculate the exact size of the state space, we have to calculate the number of games that are won in five, six, seven, and eight steps. This calculation is simple, but due to its brute-force nature, it is beyond our scope. Therefore, we will settle on the magnitude of the state space.
Note
After generating all possible tic-tac-toe games, researchers counted 255,168 possible games. Out of those games, 131,184 were won by the first player, 77,904 were won by the second player, and 46,080 games ended with a draw. Visit http://www.half-real.net/tictactoe/allgamesoftictactoe.zip to download all possible tic-tac-toe games.
Even a simple game such as tic-tac-toe has a lot of states. Just imagine how hard it would be to start exploring all possible chess games. Therefore, we can conclude that brute-force searching is rarely ideal.
Exercise 1.02: Creating an AI with Random Behavior for the Tic-Tac-Toe Game
In this exercise, we'll create a framework for the tic-tac-toe game for experimentation. We will be modeling the game on the assumption that the AI player always starts the game. You will create a function that prints your internal representation, allows your opponent to enter a move randomly, and determines whether a player has won.
Note
To ensure that this happens correctly, you will need to have completed the previous exercise.
The following steps will help you to complete this exercise:
- Begin by opening a new Jupyter Notebook file.
- We will import the choice function from the random library:
from random import choice
- Now, model the nine cells in a simple string for simplicity. A nine-character long Python string stores these cells in the following order: "123456789". Let's determine the index triples that must contain matching signs so that a player wins the game:
combo_indices = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6],
[1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
- Define the sign constants for empty cells, the AI, and the opponent player:
EMPTY_SIGN = '.'
AI_SIGN = 'X'
OPPONENT_SIGN = 'O'
In the preceding code snippet, we have assigned a different sign for the AI and the player.
- Create a function that prints a board. We will add an empty row before and after the board so that we can easily read the game state:
def print_board(board):
print(" ")
print(' '.join(board[:3]))
print(' '.join(board[3:6]))
print(' '.join(board[6:]))
print(" ")
- Describe a move of the human player. The input arguments are the boards, the row numbers from 1 to 3, and the column numbers from 1 to 3. The return value of this function is a board containing the new move:
def opponent_move(board, row, column):
index = 3 * (row - 1) + (column - 1)
if board[index] == EMPTY_SIGN:
return board[:index] + OPPONENT_SIGN + board[index+1:]
return board
Here, we have defined a function called opponent_move that will help us to calculate the index of the board based on the input (row and column). You will be able to see the resulting position on the board.
- Now, we need to define a random move on the part of the AI player. We will generate all possible moves with the all_moves_from_board function, and then select a random move from the list of possible moves:
def all_moves_from_board(board, sign):
move_list = []
for i, v in enumerate(board):
if v == EMPTY_SIGN:
move_list.append(board[:i] + sign + board[i+1:])
return move_list
def ai_move(board):
return choice(all_moves_from_board(board, AI_SIGN))
In the preceding code snippet, we defined a function called all_moves_from_board that goes through all the indexes on the board and checks whether they are empty (v == EMPTY_SIGN). If that's the case, this means that the move can be played and that the index has been added to a list of moves (move_list). Finally, we defined the ai_move function in order to randomly let the AI choose an index that is equal to a move in the game.
- Determine whether a player has won the game:
def game_won_by(board):
for index in combo_indices:
if board[index[0]] == board[index[1]] ==
board[index[2]] != EMPTY_SIGN:
return board[index[0]]
return EMPTY_SIGN
In the preceding code snippet, we have defined the game_won_by function, which checks whether the board contains a combo of three identical indexes from the combo_indices variable to end the game.
- Finally, create a game loop so that we can test the interaction between the computer player and the human player. We will conduct a brute-force search in the following examples:
def game_loop():
board = EMPTY_SIGN * 9
empty_cell_count = 9
is_game_ended = False
while empty_cell_count > 0 and not is_game_ended:
if empty_cell_count % 2 == 1:
board = ai_move(board)
else:
row = int(input('Enter row: '))
col = int(input('Enter column: '))
board = opponent_move(board, row, col)
print_board(board)
is_game_ended = game_won_by(board) != EMPTY_SIGN
empty_cell_count = sum(1 for cell in board
if cell == EMPTY_SIGN)
print('Game has been ended.')
In the preceding code snippet, we defined the function, which can be broken down into various parts.
The first part is to initialize the board and fill it with empty signs (board = EMPTY_SIGN * 9). Then, we create a counter of the empty cell, which will help us to create a loop and determine the AI's turn.
The second part is to create a function for the player and the AI engine to play the game against each other. As soon as one player makes a move, the empty_cell_count variable will decrease by 1. The loop will keep going until either the game_won_by function finds a winner or there are no more possible moves on the board.
- Use the game_loop function to run the game:
game_loop()
The expected output (partially shown) is this:
Figure 1.8: Final output (partially shown) of the game
Note
To access the source code for this specific section, please refer to https://packt.live/3fUws2l.
You can also run this example online at https://packt.live/3hVzjcT. You must execute the entire Notebook in order to get the desired result.
By completing this exercise, you have seen that even an opponent who is playing randomly may win from time to time if their opponent makes a mistake.
Activity 1.01: Generating All Possible Sequences of Steps in a Tic-Tac-Toe Game
This activity will explore the combinatorial explosion that is possible when two players play randomly. We will be using a program that, building on the previous results, generates all possible sequences of moves between a computer player and a human player.
Let's assume that the human player may make any possible move. In this example, given that the computer player is playing randomly, we will examine the wins, losses, and draws belonging to two randomly playing players:
The following steps will help you to complete this activity:
- Reuse all the function codes of Steps 2–9 from the previous Exercise 1.02, Creating an AI with Random Behavior for the Tic-Tac-Toe Game.
- Create a function that maps the all_moves_from_board function on each element of a list of board spaces/squares. This way, we will have all of the nodes of a decision tree. The decision tree starts with [ EMPTY_SIGN * 9 ] and expands after each move.
- Create a filter_wins function that takes finished games out of the list of moves and appends them in an array containing the board states won by the AI player and the opponent player.
- Create a count_possibilities function that prints and returns the number of decision tree leaves that ended with a draw, were won by the first player, and were won by the second player:
- We have up to nine steps in each state. In the 0th, 2nd, 4th, 6th, and 8th iterations, the AI player moves. In all other iterations, the opponent moves. We create all possible moves in all steps and take out finished games from the move list.
- Finally, execute the number of possibilities to experience the combinatorial explosion.
The expected output is this:
step 0. Moves: 1
step 1. Moves: 9
step 2. Moves: 72
step 3. Moves: 504
step 4. Moves: 3024
step 5. Moves: 13680
step 6. Moves: 49402
step 7. Moves: 111109
step 8. Moves: 156775
First player wins: 106279
Second player wins: 68644
Draw 91150
Total 266073
Note
The solution to this activity can be found on page 322.
So far, we've understood the significance of an intelligent agent. We also examined the game states for a game AI. Now, we will focus on how to create and introduce intelligence to an agent.
We will look at reducing the number of states in the state space, analyze the stages that a game board can undergo, and make the environment work in such a way that we win.
Have a look at the following exercise, where we'll teach an intelligent agent to win.
Exercise 1.03: Teaching the Agent to Win
In this exercise, we will see how the steps needed to win can be reduced. We will be making the agent that we developed in the previous section activity detect situations where it can win a game.
The following steps will help you to complete this exercise:
- Open a new Jupyter Notebook file.
- Reuse the previous code from Steps 2–6 from Activity 1, Generating All Possible Sequences of Steps in a Tic-Tac-Toe Game.
- Define two functions, ai_move and all_moves_from_board.
We create ai_move so that it returns a move that will consider its own previous moves. If the game can be won in that move, ai_move will select that move:
def ai_move(board):
new_boards = all_moves_from_board(board, AI_SIGN)
for new_board in new_boards:
if game_won_by(new_board) == AI_SIGN:
return new_board
return choice(new_boards)
In the preceding code snippet, we have defined the ai_move function, which will make the AI choose a winning move from a list of all the possible moves from the current state of the game if it's applicable. If not, it will still choose a random move.
- Next, test the code snippet with a game loop. Whenever the AI has the opportunity to win the game, it will always place the X in the correct cell:
game_loop()
The expected output is this:
Figure 1.9: The agent winning the game
- Now, count all the possible moves. To do this, we must change the all_moves_from_board function to include this improvement. We must do this so that, if the game is won by AI_SIGN, it will return that value:
def all_moves_from_board(board, sign):
move_list = []
for i, v in enumerate(board):
if v == EMPTY_SIGN:
new_board = board[:i] + sign + board[i+1:]
move_list.append(new_board)
if game_won_by(new_board) == AI_SIGN:
return [new_board]
return move_list
In the preceding code snippet, we have defined a function to generate all possible moves. As soon as we find a move that wins the game for the AI, we return it. We do not care whether the AI has multiple options to win the game in one move – we just return the first possibility. If the AI cannot win, we return all possible moves. Let's see what this means in terms of counting all of the possibilities at each step.
- Enter the following function to find all the possibilities.
first_player, second_player,
draw, total = count_possibilities()
The expected output is this:
step 0. Moves: 1
step 1. Moves: 9
step 2. Moves: 72
step 3. Moves: 504
step 4. Moves: 3024
step 5. Moves: 8525
step 6. Moves: 28612
step 7. Moves: 42187
step 8. Moves: 55888
First player wins: 32395
Second player wins: 23445
Draw 35544
Total 91384
Note
To access the source code for this specific section, please refer to https://packt.live/317pyTa.
You can also run this example online at https://packt.live/2YnLpDS. You must execute the entire Notebook in order to get the desired result.
With that, we have seen that the AI is still not winning most of the time. This means that we need to introduce more concepts to the AI to make it stronger. To teach the AI how to win, we need to teach it how to make defensive moves against losses.
Defending the AI against Losses
In the next activity, we will make the AI computer player play better compared to our previous exercise so that we can reduce the state space and the number of losses.
Activity 1.02: Teaching the Agent to Realize Situations When It Defends Against Losses
In this activity, we will force the computer to defend against a loss if the player puts their third sign in a row, column, or diagonal line:
- Reuse all the code from Steps 2–6 from the previous, Exercise 1.03, Teaching the Agent to Win.
- Create a function called player_can_win that takes all the moves from the board using the all_moves_from_board function and iterates over it using a variable called next_move. On each iteration, it checks whether the game can be won by the sign, and then it returns true or false.
- Extend the AI's move so that it prefers making safe moves. A move is safe if the opponent cannot win the game in the next step.
- Test the new application. You will find that the AI has made the correct move.
- Place this logic in the state space generator and check how well the computer player is doing by generating all possible games.
The expected output is this:
step 0. Moves: 1
step 1. Moves: 9
step 2. Moves: 72
step 3. Moves: 504
step 4. Moves: 3024
step 5. Moves: 5197
step 6. Moves: 18606
step 7. Moves: 19592
step 8. Moves: 30936
First player wins: 20843
Second player wins: 962
Draw 20243
Total 42048
Note
The solution to this activity can be found on page 325.
Once we complete this activity, we notice that despite our efforts to make the AI better, it can still lose in 962 ways. We will eliminate all these losses in the next activity.
Activity 1.03: Fixing the First and Second Moves of the AI to Make It Invincible
In this activity, we will be combining our previous activities by teaching the AI how to recognize both a win and a loss so that it can focus on finding moves that are more useful than others. We will be reducing the possible games by hardcoding the first and second moves:
- Reuse the code from Steps 2–4 of the previous, Activity 1.02, Teaching the Agent to Realize Situations When It Defends Against Losses.
- Count the number of empty fields on the board and make a hardcoded move in case there are 9 or 7 empty fields. You can experiment with different hardcoded moves.
- Occupying any corner, and then occupying the opposite corner, leads to no losses. If the opponent occupies the opposite corner, making a move in the middle results in no losses.
- After fixing the first two steps, we only need to deal with 8 possibilities instead of 504. We also need to guide the AI into a state where the hardcoded rules are enough so that it never loses a game.
The expected output is this:
step 0. Moves: 1
step 1. Moves: 1
step 2. Moves: 8
step 3. Moves: 8
step 4. Moves: 48
step 5. Moves: 38
step 6. Moves: 108
step 7. Moves: 76
step 8. Moves: 90
First player wins: 128
Second player wins: 0
Draw 60
Total 188
Note
The solution to this activity can be found on page 328.
Let's summarize the important techniques that we applied to reduce the state space so far:
- Empirical simplification: We accepted that the optimal first move is a corner move. We simply hardcoded a move instead of considering alternatives to focus on other aspects of the game. In more complex games, empirical moves are often misleading. The most famous chess AI victories often contain a violation of the common knowledge of chess grand masters.
- Symmetry: After we started with a corner move, we noticed that positions 1, 3, 7, and 9 were equivalent to the perspective of winning the game. Even though we didn't take this idea further, we noticed that we could even rotate the table to reduce the state space even further and consider all four corner moves as the exact same move.
- Reduction in different permutations leading to the same state: Suppose we can make the moves A or B and suppose our opponent makes move X, where X is not equal to either move A or B. If we explore the sequence A, X, B, and we start exploring the sequence B, X, then we don't have to consider the sequence B, X, A. This is because the two sequences lead to the exact same game state, and we have already explored a state containing these three moves before, that is, A, X, and B. The order of the sequence doesn't matter as it leads to the same result. This allows us to significantly reduce the number of possible moves.
- Forced moves for the player: When a player collects two signs horizontally, vertically, or diagonally, and the third cell in the row is empty, we are forced to occupy that empty cell either to win the game or to prevent the opponent from winning the game. Forced moves may imply other forced moves, which reduces the state space even further.
- Forced moves for the opponent: When a move from the opponent is clearly optimal, it does not make sense to consider scenarios where the opponent does not make the optimal move. When the opponent can win the game by occupying a cell, it does not matter whether we go on a long exploration of the cases when the opponent misses the optimal move. We save a lot less by not exploring cases when the opponent fails to prevent us from winning the game. This is because after the opponent makes a mistake, we will simply win the game.
- Random move: When we cannot decide and don't have the capacity to search, we move randomly. Random moves are almost always inferior to a search-based educated guess, but at times, we have no other choice.
Heuristics
In this section, we will formalize informed search techniques by defining and applying heuristics to guide our search. We will be looking at heuristics and creating them in the sections ahead.
Uninformed and Informed Searches
In the tic-tac-toe example, we implemented a greedy algorithm that first focused on winning, and then focused on not losing. When it comes to winning the game immediately, the greedy algorithm is optimal because there is never a better step than winning the game. When it comes to not losing, it matters how we avoid the loss. Our algorithm simply choses a random safe move without considering how many winning opportunities we have created.
BFS and DFS are part of uninformed searching because they consider all possible states in the game, which can be very time-consuming. On the other hand, heuristic informed searches will explore the space of available states intelligently in order to reach the goal faster.
Creating Heuristics
If we want to make better decisions, we apply heuristics to guide the search in the right direction by considering long-term benefits. This way, we can make a more informed decision in the present based on what could happen in the future. This can also help us solve problems faster.
We can construct heuristics as follows:
- In terms of the utility of making a move in the game
- In terms of the utility of a given game state from the perspective of a player
- In terms of the distance from our goal
Heuristics are functions that evaluate a game state or a transition to a new game state based on their utility. Heuristics are the cornerstones of making a search problem informed.
In this book, we will use utility and cost as negated terms. Maximizing utility and minimizing the cost of a move are considered synonyms.
A commonly used example of a heuristic evaluation function occurs in pathfinding problems. Suppose we are looking to reach a destination or a goal. Each step has an associated cost symbolizing the travel distance. Our goal is to minimize the cost of reaching the destination or goal (minimizing the travel distance).
One example of heuristic evaluation for solving this pathfinding problem will be to take the coordinates between the current state (position) and the goal (destination) and calculate the distance between these two points. The distance between two points is the length of the straight line connecting the points. This heuristic is called the Euclidean distance (as shown in the Figure 1.10).
Now, suppose we define our pathfinding problem in a maze, where we can only move up, down, left, or right. There are a few obstacles in the maze that block our moves, so using the Euclidean distance is not ideal. A better heuristic would be to use the Manhattan distance, which can be defined as the sum of the horizontal and vertical distances between the coordinates of the current state and the goal.
Admissible and Non-Admissible Heuristics
The two heuristics we just defined regarding pathfinding problems are called admissible heuristics when they're used on their given problem domain.
Admissible means that we may underestimate the cost of reaching the end state but that we never overestimate it. Later, we will explore an algorithm that finds the shortest path between the current state and the goal state. The optimal nature of this algorithm depends on whether we can define an admissible heuristic function.
An example of a non-admissible heuristic would be the Euclidean distance that's applied to a real-world map.
Imagine that we want to move from point A to point B in the city of Manhattan. Here, the Euclidean distance will be the straight line between the two points, but, as we know, we cannot just go straight in a city such as Manhattan (unless we can fly). In this case, the Euclidean distance is underestimating the cost of reaching the goal. A better heuristic would be the Manhattan distance:
Figure 1.10: Euclidian distance (blue line) and Manhattan distance (red line) in the city of Manhattan
Note
The preceding map of Manhattan is sourced from Google Maps.
Since we overestimated the cost of traveling from the current node to the goal, the Euclidean distance is not admissible when we cannot move diagonally.
Heuristic Evaluation
We can create a heuristic evaluation for our tic-tac-toe game state from the perspective of the starting player by defining the utility of a move.
Heuristic 1: Simple Evaluation of the Endgame
Let's define a simple heuristic by evaluating a board. We can set the utility for the game as one of the following:
- +1, if the state implies that the AI player will win the game
- -1, if the state implies that the AI player will lose the game
- 0, if a draw has been reached or no clear winner can be identified from the current state
This heuristic is simple because anyone can look at a board and analyze whether a player is about to win.
The utility of this heuristic depends on whether we can play many moves in advance. Notice that we cannot even win the game within five steps. In Activity 1.01, Generating All Possible Sequences of Steps in a Tic-Tac-Toe Game, we saw that by the time we reach step five, we have 13,680 possible combinations leading to it. In most of these 13,680 cases, our heuristic returns zero as we can't identify a clear winner yet.
If our algorithm does not look deeper than these five steps, we are completely clueless on how to start the game. Therefore, we should invent a better heuristic.
Heuristic 2: Utility of a Move
Let's change the utility for the game as follows:
- Two AI signs in a row, column, or diagonal, and the third cell is empty: +1000 for the empty cell.
- The opponent has two signs in a row, column, or diagonal, and the third cell is empty: +100 for the empty cell.
- One AI sign in a row, column, or diagonal, and the other two cells are empty: +10 for the empty cells.
- No AI or opponent signs in a row, column, or diagonal: +1 for the empty cells.
- Occupied cells get a value of minus infinity. In practice, due to the nature of the rules, -1 will also do.
Why do we use a multiplicative factor of 10 for the first three rules compared to the fourth one? We do this because there are eight possible ways of making three in a row, column, and diagonal. So, even by knowing nothing about the game, we are certain that a lower-level rule may not accumulate to overriding a higher-level rule. In other words, we will never defend against the opponent's moves if we can win the game.
Note
As the job of our opponent is also to win, we can compute this heuristic from the opponent's point of view. Our task is to maximize this value, too, so that we can defend against the optimal plays of our opponent. This is the idea behind the Minmax algorithm as well, which will be covered later in this chapter. If we wanted to convert this heuristic into a heuristic that describes the current board, we could compute the heuristic value for all open cells and take the maximum of the values for the AI character so that we can maximize our utility.
For each board, we will create a utility matrix.
For example, consider the following board, with O signs as the player and X signs as the AI:
Figure 1.11: Tic-tac-toe game state
From here, we can construct its utility matrix shown in the following figure:
Figure 1.12: Tic-tac-toe game utility matrix
On the second row, the left cell is not beneficial if we were to select it. Note that if we had a more optimal utility function, we would reward blocking the opponent.
The two cells of the third column both get a 10-point boost for two in a row.
The top-right cell also gets 100 points for defending against the diagonal of the opponent.
From this matrix, evidently, we should choose the top-right move. At any stage of the game, we were able to define the utility of each cell; this was a static evaluation of the heuristic function.
We can use this heuristic to guide us toward an optimal next move or to give a more educated score on the current board by taking the maximum of these values. We have technically used parts of this heuristic in the form of hardcoded rules. Note, though, that the real utility of heuristics is not the static evaluation of a board, but the guidance it provides for limiting the search space.
Exercise 1.04: Tic-Tac-Toe Static Evaluation with a Heuristic Function
In this exercise, you will be performing a static evaluation on the tic-tac-toe game using a heuristic function.
The following steps will help you to complete this exercise:
- Open a new Jupyter Notebook file.
- Reuse the code from Steps 2–6 of Activity 1.01, Generating All Possible Sequences of Steps in a Tic-Tac-Toe Game.
- Create a function that takes the board as input and returns 0 if the cell is empty, and -1 if it's not empty:
def init_utility_matrix(board):
return [0 if cell == EMPTY_SIGN
else -1 for cell in board]
- Next, create a function that takes the utility vector of possible moves, takes three indices inside the utility vector representing a triple, and returns a function, as shown in the following code snippet:
def generate_add_score(utilities, i, j, k):
def add_score(points):
if utilities[i] >= 0:
utilities[i] += points
if utilities[j] >= 0:
utilities[j] += points
if utilities[k] >= 0:
utilities[k] += points
return add_score
In the preceding code snippet, the returned function will expect a points parameter and the utilities vector as input and will add points to each cell in (i, j, k), as long as the original value of that cell is non-negative (>=0). In other words, we increased the utility of empty cells only.
- Now, create the utility matrix belonging to any board constellation where you will add the generate_add_score function defined previously to update the score. You will also implement the rules that we discussed prior to this activity. These rules are as follows:
Two AI signs in a row, column, or diagonal, and the third cell is empty: +1000 for the empty cell.
The opponent has two signs in a row, column, or diagonal, and the third cell is empty: +100 for the empty cell.
One AI sign in a row, column, or diagonal, and the other two cells are empty: +10 for the empty cells.
No AI or opponent signs in a row, column, or diagonal: +1 for the empty cells.
Let's create the utility matrix now:
def utility_matrix(board):
utilities = init_utility_matrix(board)
for [i, j, k] in combo_indices:
add_score = generate_add_score(utilities, i, j, k)
triple = [board[i], board[j], board[k]]
if triple.count(EMPTY_SIGN) == 1:
if triple.count(AI_SIGN) == 2:
add_score(1000)
elif triple.count(OPPONENT_SIGN) == 2:
add_score(100)
elif triple.count(EMPTY_SIGN) == 2 and
triple.count(AI_SIGN) == 1:
add_score(10)
elif triple.count(EMPTY_SIGN) == 3:
add_score(1)
return utilities
- Create a function that selects the move with the highest utility value. If multiple moves have the same utility, the function returns both moves:
def best_moves_from_board(board, sign):
move_list = []
utilities = utility_matrix(board)
max_utility = max(utilities)
for i, v in enumerate(board):
if utilities[i] == max_utility:
move_list.append(board[:i]
+ sign
+ board[i+1:])
return move_list
def all_moves_from_board_list(board_list, sign):
move_list = []
get_moves = best_moves_from_board if sign
== AI_SIGN else all_moves_from_board
for board in board_list:
move_list.extend(get_moves(board, sign))
return move_list
- Now, run the application, as shown in the following code snippet:
first_player, second_player,
draw, total = count_possibilities()
The expected output is this:
step 0. Moves: 1
step 1. Moves: 1
step 2. Moves: 8
step 3. Moves: 24
step 4. Moves: 144
step 5. Moves: 83
step 6. Moves: 214
step 7. Moves: 148
step 8. Moves: 172
First player wins: 504
Second player wins: 12
Draw 91
Total 607
Note
To access the source code for this specific section, please refer to https://packt.live/2VpGyAv.
You can also run this example online at https://packt.live/2YnyO3K. You must execute the entire Notebook in order to get the desired result.
By completing this exercise, we have observed that the AI is underperforming compared to our previous activity, Activity 1.03, Fixing the First and Second Moves of the AI to Make It Invincible. In this situation, hardcoding the first two moves was better than setting up the heuristic, but this is because we haven't set up the heuristic properly.
Using Heuristics for an Informed Search
We have not experienced the real power of heuristics yet as we made moves without the knowledge of the effects of our future moves, thereby effecting reasonable play from our opponents.
Therefore, a more accurate heuristic leads to more losses than simply hardcoding the first two moves in the game. Note that in the previous section, we selected these two moves based on the statistics we generated based on running the game with fixed first moves. This approach is essentially what heuristic search should be all about.
Types of Heuristics
Static evaluation cannot compete with generating hundreds of thousands of future states and selecting a play that maximizes our rewards. This is because our heuristics are not exact and are likely not admissible either.
We saw in the preceding exercise that heuristics are not always optimal. We came up with rules that allowed the AI to always win the game or finish with a draw. These heuristics allowed the AI to win very frequently, at the expense of losing in a few cases. A heuristic is said to be admissible if we underestimate the utility of a game state, but we never overestimate it.
In the tic-tac-toe example, we likely overestimated the utility in a few game states, and why is that? Because we ended up with a loss 12 times. A few of the game states that led to a loss had a maximum heuristic score. To prove that our heuristic is not admissible, all we need to do is find a potentially winning game state that we ignored while choosing a game state that led to a loss.
There are two more features that describe heuristics, that is, optimal and complete:
- Optimal heuristics always find the best possible solution.
- Complete heuristics has two definitions, depending on how we define the problem domain. In a loose sense, a heuristic is said to be complete if it always finds a solution. In a strict sense, a heuristic is said to be complete if it finds all possible solutions. Our tic-tac-toe heuristic is not complete because we ignored many possible winning states on purpose, favoring a losing state.
As you can see, defining an accurate heuristic requires a lot of details and thinking in order to obtain a perfect AI agent. If you are not correctly estimating the utility in the game states, then you can end up with an AI underperforming hardcoded rules.
In the next section, we'll look at a better approach to executing the shortest pathfinding between the current state and the goal state.
Pathfinding with the A* Algorithm
In the first two sections, we learned how to define an intelligent agent and how to create a heuristic that guides the agent toward a desired state. We learned that this was not perfect because, at times, we ignored a few winning states in favor of a few losing states.
Now, we will learn about a structured and optimal approach so that we can execute a search for finding the shortest path between the current state and the goal state by using the A* ("A star" instead of "A asterisk") algorithm.
Have a look at the following figure:
Figure 1.13: Finding the shortest path in a maze
For a human, it is simple to find the shortest path by merely looking at the figure. We can conclude that there are two potential candidates for the shortest path: route one starts upward, and route two starts to the left. However, the AI does not know about these options. In fact, the most logical first step for a computer player would be moving to the square denoted by the number 3 in the following figure.
Why? Because this is the only step that decreases the distance between the starting state and the goal state. All the other steps initially move away from the goal state:
Figure 1.14: Shortest pathfinding game board with utilities
In the next exercise, we'll see how the BFS algorithm performs on the pathfinding problem before introducing you to the A* algorithm.
Exercise 1.05: Finding the Shortest Path Using BFS
In this exercise, we will be finding the shortest path to our goal using the BFS algorithm.
The following steps will help you to complete this exercise:
- Open a new Jupyter Notebook file.
- Begin by importing the math library:
import math
- Next, describe the board, the initial state, and the final state using Python. Create a function that returns a list of possible successors. Use tuples, where the first coordinate denotes the row number from 1 to 7 and the second coordinate denotes the column number from 1 to 9:
size = (7, 9)
start = (5, 3)
end = (6, 9)
obstacles = {(3, 4), (3, 5), (3, 6), (3, 7), (3, 8),
(4, 5), (5, 5), (5, 7), (5, 9), (6, 2),
(6, 3), (6, 4), (6, 5), (6, 7),(7, 7)}
- Next, use array comprehension to generate the successor states, as shown in the following code:
def successors(state, visited_nodes):
(row, col) = state
(max_row, max_col) = size
succ_states = []
if row > 1:
succ_states += [(row-1, col)]
if col > 1:
succ_states += [(row, col-1)]
if row < max_row:
succ_states += [(row+1, col)]
if col < max_col:
succ_states += [(row, col+1)]
return [s for s in succ_states if s not in
visited_nodes if s not in obstacles]
The function is generating all the possible moves from a current field that does not end up being blocked by an obstacle. We also add a filter to exclude moves that return to a field we have visited already to avoid infinite loops.
- Next, implement the initial costs, as shown in the following code snippet:
def initialize_costs(size, start):
(h, w) = size
costs = [[math.inf] * w for i in range(h)]
(x, y) = start
costs[x-1][y-1] = 0
return costs
- Now, implement the updated costs using costs, current_node, and successor_node:
def update_costs(costs, current_node, successor_nodes):
new_cost = costs[current_node[0]-1]
[current_node[1]-1] + 1
for (x, y) in successor_nodes:
costs[x-1][y-1] = min(costs[x-1][y-1], new_cost)
- Finally, implement the BFS algorithm to search the state of the tree and save the result in a variable called bfs:
def bfs_tree(node):
nodes_to_visit = [node]
visited_nodes = []
costs = initialize_costs(size, start)
while len(nodes_to_visit) > 0:
current_node = nodes_to_visit.pop(0)
visited_nodes.append(current_node)
successor_nodes = successors(current_node,
visited_nodes)
update_costs(costs, current_node, successor_nodes)
nodes_to_visit.extend(successor_nodes)
return costs
bfs = bfs_tree(start)
bfs
In the preceding code snippet, we have reused the bfs_tree function that we looked at earlier in the Breadth First Search section of this book. However, we added the update_costs function to update the costs.
The expected output is this:
[[6, 5, 4, 5, 6, 7, 8, 9, 10],
[5, 4, 3, 4, 5, 6, 7, 8, 9],
[4, 3, 2, inf, inf, inf, inf, inf, 10],
[3, 2, 1, 2, inf, 12, 13, 12, 11],
[2, 1, 0, 1, inf, 11, inf, 13, inf],
[3, inf, inf, inf, inf, 10, inf, 14, 15],
[4, 5, 6, 7, 8, 9, inf, 15, 16]]
Here, you can see that a simple BFS algorithm successfully determines the cost from the start node to any nodes, including the target node.
- Now, measure the number of steps required to find the goal node and save the result in the bfs_v variable, as shown in the following code snippet:
def bfs_tree_verbose(node):
nodes_to_visit = [node]
visited_nodes = []
costs = initialize_costs(size, start)
step_counter = 0
while len(nodes_to_visit) > 0:
step_counter += 1
current_node = nodes_to_visit.pop(0)
visited_nodes.append(current_node)
successor_nodes = successors(current_node,
visited_nodes)
update_costs(costs, current_node, successor_nodes)
nodes_to_visit.extend(successor_nodes)
if current_node == end:
print('End node has been reached in ',
step_counter, ' steps')
return costs
return costs
bfs_v = bfs_tree_verbose(start)
bfs_v
In the preceding code snippet, we have added a step counter variable in order to print the number of steps at the end of the search.
The expected output is this:
End node has been reached in 110 steps
[[6, 5, 4, 5, 6, 7, 8, 9, 10],
[5, 4, 3, 4, 5, 6, 7, 8, 9],
[4, 3, 2, inf, inf, inf, inf, inf, 10],
[3, 2, 1, 2, inf, 12, 13, 12, 11],
[2, 1, 0, 1, inf, 11, inf, 13, inf],
[3, inf, inf, inf, inf, 10, inf, 14, 15],
[4, 5, 6, 7, 8, 9, inf, 15, 16]]
Note
To access the source code for this specific section, please refer to https://packt.live/3fMYwEt.
You can also run this example online at https://packt.live/3duuLqp. You must execute the entire Notebook in order to get the desired result.
In this exercise, we used the BFS algorithm to find the shortest path to the goal. It took BFS 110 steps to reach the goal. Now, we will learn about an algorithm that can find the shortest path from the start node to the goal node: the A* algorithm.
Introducing the A* Algorithm
A* is a complete and optimal heuristic search algorithm that finds the shortest possible path between the current game state and the winning state. The definition of complete and optimal in this state are as follows:
- Complete means that A* always finds a solution.
- Optimal means that A* will find the best solution.
To set up the A* algorithm, we need the following:
- An initial state
- A description of the goal states
- Admissible heuristics to measure progress toward the goal state
- A way to generate the next steps toward the goal
Once the setup is complete, we execute the A* algorithm using the following steps on the initial state:
- We generate all possible next steps.
- We store these children in the order of their distance from the goal.
- We select the child with the best score first and repeat these three steps on the child with the best score as the initial state. This is the shortest path to get to a node from the starting node.
Let's take, for example, the following figure:
Figure 1.15: Tree with heuristic distance
The first step will be to generate all the possible moves from the origin, A, which is moving from A to B (A,B) or to C (A,C).
The second step is to use the heuristic (the distance) to order the two possible moves, (A,B), with 10, which is shorter compared to (A,C) with 100.
The third step is to choose the shortest heuristic, which is (A,B), and move to B.
Now, we will repeat the same steps with B as the origin.
At the end, we will reach the goal F with the path (A,B,D,F) with a cumulative heuristic of 24. If we were following another path, such as (A,B,E,F), the cumulative heuristic will be 30, which is higher than the shortest path.
We did not even look at (A,C,F) as it was already way over the shortest path.
In pathfinding, a good heuristic is the Euclidean distance. If the current node is (x, y) and the goal node is (u, v), then we have the following:
distance_from_end( node ) = sqrt( abs( x – u ) ** 2 + abs( y – v ) ** 2 )
Here, distance_from_end(node) is an admissible heuristic estimation showing how far we are from the goal node.
We also have the following:
- sqrt is the square root function. Do not forget to import it from the math library.
- abs is the absolute value function, that is, abs( -2 ) = abs( 2 ) = 2.
- x ** 2 is x raised to the second power.
We will use the distance_from_start matrix to store the distances from the start node. In the algorithm, we will refer to this cost matrix as distance_from_start(n1). For any node, n1, that has coordinates (x1, y1), this distance is equivalent to distance_from_start[x1][y1].
We will use the succ(n) notation to generate a list of successor nodes from n.
Note
The # symbol in the code snippet below denotes a code comment. Comments are added into code to help explain specific bits of logic. The triple-quotes ( """ ) shown in the code snippet below are used to denote the start and end points of a multi-line code comment. Comments are added into code to help explain specific bits of logic.
Have a look at the pseudocode of the algorithm:
frontier = [start], internal = {}
# Initialize the costs matrix with each cell set to infinity.
# Set the value of distance_from_start(start) to 0.
while frontier is not empty:
"""
notice n has the lowest estimated total
distance between start and end.
"""
n = frontier.pop()
# We'll learn later how to reconstruct the shortest path
if n == end:
return the shortest path.
internal.add(n)
for successor s in succ(n):
if s in internal:
continue # The node was already examined
new_distance = distance_from_start(n) + distance(n, s)
if new_distance >= distance_from_start(s):
"""
This path is not better than the path we have
already examined.
"""
continue
if s is a member of frontier:
update the priority of s
else:
Add s to frontier.
Regarding the retrieval of the shortest path, we can use the costs matrix. This matrix contains the distance of each node on the path from the start node. As cost always decreases when walking backward, all we need to do is start with the end node and walk backward greedily toward decreasing costs:
path = [end_node], distance = get_distance_from_start( end_node )
while the distance of the last element in the path is not 0:
for each neighbor of the last node in path:
new_distance = get_distance_from_start( neighbor )
if new_distance < distance:
add neighbor to path, and break out from the for loop
return path
A* shines when we have one start state and one goal state. The complexity of the A* algorithm is O( E ), where E stands for all possible edges in the field. In our example, we have up to four edges leaving any node: up, down, left, and right.
Note
To sort the frontier list in the proper order, we must use a special Python data structure: a priority queue.
Have a look at the following example:
# Import heapq to access the priority queue
import heapq
# Create a list to store the data
data = []
"""
Use heapq.heappush to push (priorityInt, value)
pairs to the queue
"""
heapq.heappush(data, (2, 'first item'))
heapq.heappush(data, (1, 'second item'))
"""
The tuples are stored in data in the order
of ascending priority
"""
[(1, 'second item'), (2, 'first item')]
"""
heapq.heappop pops the item with the lowest score
from the queue
"""
heapq.heappop(data)
The expected output is this:
(1, 'second item')
The data still contains the second item. If you type in the following command, you will be able to see it:
data
The expected output is this:
[(2, 'first item')]
Why is it important that the heuristic being used by the algorithm is admissible?
Because this is how we guarantee the optimal nature of the algorithm. For any node x, we are measuring the sum of the distances from the start node to x. This is the estimated distance from x to the end node. If the estimation never overestimates the distance from x to the end node, we will never overestimate the total distance. Once we are at the goal node, our estimation is zero, and the total distance from the start to the end becomes an exact number.
We can be sure that our solution is optimal because there are no other items in the priority queue that have a lower estimated cost. Given that we never overestimate our costs, we can be sure that all of the nodes in the frontier of the algorithm have either similar total costs or higher total costs than the path we found.
In the following example, we can see how to implement the A* algorithm to find the path with the lowest cost:
Figure 1.16: Shortest pathfinding game board
We import math and heapq:
import math
import heapq
Next, we'll reuse the initialization code from Steps 2–5 of the previous, Exercise 1.05, Finding the Shortest Path Using BFS.
Note
We have omitted the function to update costs because we will do so within the A* algorithm:
Next, we need to initialize the A* algorithm's frontier and internal lists. For frontier, we will use a Python PriorityQueue. Do not execute this code directly; we will use these four lines inside the A* search function:
frontier = []
internal = set()
heapq.heappush(frontier, (0, start))
costs = initialize_costs(size, start)
Now, it is time to implement a heuristic function that measures the distance between the current node and the goal node using the algorithm we saw in the heuristic section:
def distance_heuristic(node, goal):
(x, y) = node
(u, v) = goal
return math.sqrt(abs(x - u) ** 2 + abs(y - v) ** 2)
The final step will be to translate the A* algorithm into functioning code:
def astar(start, end):
frontier = []
internal = set()
heapq.heappush(frontier, (0, start))
costs = initialize_costs(size, start)
def get_distance_from_start(node):
return costs[node[0] - 1][node[1] - 1]
def set_distance_from_start(node, new_distance):
costs[node[0] - 1][node[1] - 1] = new_distance
while len(frontier) > 0:
(priority, node) = heapq.heappop(frontier)
if node == end:
return priority
internal.add(node)
successor_nodes = successors(node, internal)
for s in successor_nodes:
new_distance = get_distance_from_start(node) + 1
if new_distance < get_distance_from_start(s):
set_distance_from_start(s, new_distance)
# Filter previous entries of s
frontier = [n for n in frontier if s != n[1]]
heapq.heappush(frontier,
(new_distance
+ distance_heuristic(s, end), s))
astar(start, end)
The expected output is this:
15.0
There are a few differences between our implementation and the original algorithm.
We defined a distance_from_start function to make it easier and more semantic to access the costs matrix. Note that we number the node indices starting with 1, while in the matrix, indices start with zero. Therefore, we subtract 1 from the node values to get the indices.
When generating the successor nodes, we automatically ruled out nodes that are in the internal set. successors = succ(node, internal) makes sure that we only get the neighbors whose examination is not closed yet, meaning that their score is not necessarily optimal.
Therefore, we may skip the step check since internal nodes will never end up in succ(n).
Since we are using a priority queue, we must determine the estimated priority of nodes before inserting them. However, we will only insert the node in the frontier if we know that this node does not have an entry with a lower score.
It may happen that nodes are already in the frontier queue with a higher score. In this case, we remove this entry before inserting it into the right place in the priority queue. When we find the end node, we simply return the length of the shortest path instead of the path itself.
To follow what the A* algorithm does, execute the following example code and observe the logs:
def astar_verbose(start, end):
frontier = []
internal = set()
heapq.heappush(frontier, (0, start))
costs = initialize_costs(size, start)
def get_distance_from_start(node):
return costs[node[0] - 1][node[1] - 1]
def set_distance_from_start(node, new_distance):
costs[node[0] - 1][node[1] - 1] = new_distance
steps = 0
while len(frontier) > 0:
steps += 1
print('step ', steps, '. frontier: ', frontier)
(priority, node) = heapq.heappop(frontier)
print('node ', node,
'has been popped from frontier with priority',
priority)
if node == end:
print('Optimal path found. Steps: ', steps)
print('Costs matrix: ', costs)
return priority
internal.add(node)
successor_nodes = successors(node, internal)
print('successor_nodes', successor_nodes)
for s in successor_nodes:
new_distance = get_distance_from_start(node) + 1
print('s:', s, 'new distance:', new_distance,
' old distance:', get_distance_from_start(s))
if new_distance < get_distance_from_start(s):
set_distance_from_start(s, new_distance)
# Filter previous entries of s
frontier = [n for n in frontier if s != n[1]]
new_priority = new_distance
+ distance_heuristic(s, end)
heapq.heappush(frontier, (new_priority, s))
print('Node', s,
'has been pushed to frontier with priority',
new_priority)
print('Frontier', frontier)
print('Internal', internal)
print(costs)
astar_verbose(start, end)
Here, we build the astar_verbose function by reusing the code from the astar function and adding print functions in order to create a log.
The expected output is this:
Figure 1.17: Astar function logs
We have seen that the A* search returns the right values. The question is, how can we reconstruct the whole path?
For this, we remove the print statements from the code for clarity and continue with the A* algorithm that we implemented in the previous step. Instead of returning the length of the shortest path, we have to return the path itself. We will write a function that extracts this path by walking backward from the end node, analyzing the costs matrix. Do not define this function globally yet. We define it as a local function in the A* algorithm that we created previously:
def get_shortest_path(end_node):
path = [end_node]
distance = get_distance_from_start(end_node)
while distance > 0:
for neighbor in successors(path[-1], []):
new_distance = get_distance_from_start(neighbor)
if new_distance < distance:
path += [neighbor]
distance = new_distance
break # for
return path
Now that we've seen how to deconstruct the path, let's return it inside the A* algorithm:
def astar_with_path(start, end):
frontier = []
internal = set()
heapq.heappush(frontier, (0, start))
costs = initialize_costs(size, start)
def get_distance_from_start(node):
return costs[node[0] - 1][node[1] - 1]
def set_distance_from_start(node, new_distance):
costs[node[0] - 1][node[1] - 1] = new_distance
def get_shortest_path(end_node):
path = [end_node]
distance = get_distance_from_start(end_node)
while distance > 0:
for neighbor in successors(path[-1], []):
new_distance = get_distance_from_start(neighbor)
if new_distance < distance:
path += [neighbor]
distance = new_distance
break # for
return path
while len(frontier) > 0:
(priority, node) = heapq.heappop(frontier)
if node == end:
return get_shortest_path(end)
internal.add(node)
successor_nodes = successors(node, internal)
for s in successor_nodes:
new_distance = get_distance_from_start(node) + 1
if new_distance < get_distance_from_start(s):
set_distance_from_start(s, new_distance)
# Filter previous entries of s
frontier = [n for n in frontier if s != n[1]]
heapq.heappush(frontier,
(new_distance
+ distance_heuristic(s, end), s))
astar_with_path( start, end )
In the preceding code snippet, we have reused the a-star function defined previously with the notable difference of adding the get_shortest_path function. Then, we use this function to replace the priority queue since we want the algorithm to always choose the shortest path.
The expected output is this:
Figure 1.18: Output showing the priority queue
Technically, we do not need to reconstruct the path from the costs matrix. We could record the parent node of each node in the matrix and simply retrieve the coordinates to save a bit of searching.
We are not expecting you to understand all the preceding script as it is quite advanced, so we are going to use a library that will simplify it for us.
A* Search in Practice Using the simpleai Library
The simpleai library is available on GitHub and contains many popular AI tools and techniques.
Note
You can access this library at https://github.com/simpleai-team/simpleai. The documentation of the simpleai library can be accessed here: http://simpleai.readthedocs.io/en/latest/. To access the simpleai library, first, you have to install it.
The simpleai library can be installed as follows:
pip install simpleai
Once simpleai has been installed, you can import classes and functions from the simpleai library into a Jupyter Notebook:
from simpleai.search import SearchProblem, astar
SearchProblem gives you a frame for defining any search problems. The astar import is responsible for executing the A* algorithm inside the search problem.
For simplicity, we have not used classes in the previous code examples to focus on the algorithms in a plain old style without any clutter.
Note
Remember that the simpleai library will force us to use classes.
To describe a search problem, you need to provide the following:
- constructor: This initializes the state space, thus describing the problem. We will make the Size, Start, End, and Obstacles values available in the object by adding it to these as properties. At the end of the constructor, do not forget to call the super constructor, and do not forget to supply the initial state.
- actions( state ): This returns a list of actions that we can perform from a given state. We will use this function to generate new states. Semantically, it would make more sense to create action constants such as UP, DOWN, LEFT, and RIGHT, and then interpret these action constants as a result. However, in this implementation, we will simply interpret an action as "move to (x, y)", and represent this command as (x, y). This function contains more-or-less the logic that we implemented in the succ function previously, except that we won't filter the result based on a set of visited nodes.
- result( state0, action): This returns the new state of action that was applied to state0.
- is_goal( state ): This returns true if the state is a goal state. In our implementation, we will have to compare the state to the end state coordinates.
- cost( self, state, action, newState ): This is the cost of moving from state to newState via action. In our example, the cost of a move is uniformly 1.
Have a look at the following example:
import math
from simpleai.search import SearchProblem, astar
class ShortestPath(SearchProblem):
def __init__(self, size, start, end, obstacles):
self.size = size
self.start = start
self.end = end
self.obstacles = obstacles
super(ShortestPath,
self).__init__(initial_state=self.start)
def actions(self, state):
(row, col) = state
(max_row, max_col) = self.size
succ_states = []
if row > 1:
succ_states += [(row-1, col)]
if col > 1:
succ_states += [(row, col-1)]
if row < max_row:
succ_states += [(row+1, col)]
if col < max_col:
succ_states += [(row, col+1)]
return [s for s in succ_states
if s not in self.obstacles]
def result(self, state, action):
return action
def is_goal(self, state):
return state == end
def cost(self, state, action, new_state):
return 1
def heuristic(self, state):
(x, y) = state
(u, v) = self.end
return math.sqrt(abs(x-u) ** 2 + abs(y-v) ** 2)
size = (7, 9)
start = (5, 3)
end = (6, 9)
obstacles = {(3, 4), (3, 5), (3, 6), (3, 7), (3, 8),
(4, 5), (5, 5), (5, 7), (5, 9), (6, 2),
(6, 3), (6, 4), (6, 5), (6, 7), (7, 7)}
searchProblem = ShortestPath(size, start, end, obstacles)
result = astar(searchProblem, graph_search=True)
result.path()
In the preceding code snippet, we used the simpleai package to simplify our code. We also had to define a class called ShortestPath in order to use the package.
The expected output is this:
Figure 1.19: Output showing the queue using the simpleai library
The simpleai library made the search description a lot easier than the manual implementation. All we need to do is define a few basic methods, and then we have access to an effective search implementation.
In the next section, we will be looking at the Minmax algorithm, along with pruning.
Game AI with the Minmax Algorithm and Alpha-Beta Pruning
In the first two sections, we saw how hard it was to create a winning strategy for a simple game such as tic-tac-toe. The previous section introduced a few structures for solving search problems with the A* algorithm. We also saw that tools such as the simpleai library help us to reduce the effort we put in to describe a task with code.
We will use all of this knowledge to supercharge our game AI skills and solve more complex problems.
Search Algorithms for Turn-Based Multiplayer Games
Turn-based multiplayer games such as tic-tac-toe are similar to pathfinding problems. We have an initial state and we have a set of end states where we win the game.
The challenge with turn-based multiplayer games is the combinatorial explosion of the opponent's possible moves. This difference justifies treating turn-based games differently to a regular pathfinding problem.
For instance, in the tic-tac-toe game, from an empty board, we can select one of the nine cells and place our sign there, assuming we start the game. Let's denote this algorithm with the succ function, symbolizing the creation of successor states. Consider we have the initial state denoted by Si.
Here, we have succ(Si) returns [ S1, S2, ..., Sn ], where S1, S2, ..., Sn are successor states:
Figure 1.20: Tree diagram denoting the successor states of the function
Then, the opponent also makes a move, meaning that from each possible state, we have to examine even more states:
Figure 1.21: Tree diagram denoting parent-successor relationships
The expansion of possible future states stops in one of two cases:
- The game ends.
- Due to resource limitations, it is not worth explaining any more moves beyond a certain depth for the state of a certain utility.
Once we stop expanding, we have to make a static heuristic evaluation of the state. This is exactly what we did previously with the A* algorithm, when choosing the best move; however, we never considered future states.
Therefore, even though our algorithm became more and more complex, without using the knowledge of possible future states, we had a hard time detecting whether our current move would likely be a winning one or a losing one.
The only way for us to take control of the future was to change our heuristic while knowing how many games we would win, lose, or tie in the future. We could either maximize our wins or minimize our losses. We still did not dig deep enough to see whether our losses could have been avoided through smarter play on the part of the AI.
All these problems can be avoided by digging deeper into future states and recursively evaluating the utility of the branches.
To consider future states, we will learn about the Minmax algorithm and its variant, the NegaMax algorithm.
The Minmax Algorithm
Suppose there is a game where a heuristic function can evaluate a game state from the perspective of the AI player. For instance, we used a specific evaluation for the tic-tac-toe exercise:
- +1,000 points for a move that won the game
- +100 points for a move preventing the opponent from winning the game
- +10 points for a move creating two in a row, column, or diagonal
- +1 point for a move creating one in a row, column, or diagonal
This static evaluation is straightforward to implement on any node. The problem is that as we go deep into the tree of all possible future states, we do not yet know what to do with these scores. This is where the Minmax algorithm comes into play.
Suppose we construct a tree with each possible move that could be performed by each player up to a certain depth. At the bottom of the tree, we evaluate each option. For the sake of simplicity, let's assume that we have a search tree that appears as follows:
Figure 1.22: Example of a search tree up to a certain depth
The AI plays with X, and the player plays with O. A node with X means that it is X's turn to move. A node with O means it is O's turn to act.
Suppose there are all O leaves at the bottom of the tree, and we didn't compute any more values because of resource limitations. Our task is to evaluate the utility of the leaves:
Figure 1.23: Example of a search tree with possible moves
We have to select the best possible move from our perspective because our goal is to maximize the utility of our move. This aspiration to maximize our gains represents the Max part in the Minmax algorithm:
Figure 1.24: Example of a search tree with the best possible move
If we move one level higher, it is our opponent's turn to act. Our opponent picks the value that is the least beneficial to us. This is because our opponent's job is to minimize our chances of winning the game. This is the Min part of the Minmax algorithm:
Figure 1.25: Minimizing the chances of winning the game
At the top, we can choose between a move with utility 101 and another move with utility 21. Since we are maximizing our value, we should pick 101:
Figure 1.26: Maximizing the chances of winning the game
Let's see how we can implement this idea:
def min_max( state, depth, is_maximizing):
if depth == 0 or is_end_state( state ):
return utility( state )
if is_maximizing:
utility = 0
for s in successors( state ):
score = MinMax( s, depth - 1, false )
utility = max( utility, score )
return utility
else:
utility = infinity
for s in successors( state ):
score = MinMax( s, depth - 1, true )
utility = min( utility, score )
return utility
This is the Minmax algorithm. We evaluate the leaves from our perspective. Then, from the bottom up, we apply a recursive definition:
- Our opponent plays optimally by selecting the worst possible node from our perspective.
- We play optimally by selecting the best possible node from our perspective.
We need a few more things in order to understand the application of the Minmax algorithm on the tic-tac-toe game:
- is_end_state is a function that determines whether the state should be evaluated instead of digging deeper, either because the game has ended, or because the game is about to end using forced moves. Using our utility function, it is safe to say that as soon as we reach a score of 1,000 or higher, we have effectively won the game. Therefore, is_end_state can simply check the score of a node and determine whether we need to dig deeper.
- Although the successors function only depends on the state, it is practical to pass the information of whose turn it is to make a move. Therefore, do not hesitate to add an argument if needed; you do not have to follow the pseudo code.
- We want to minimize our efforts in implementing the Minmax algorithm. For this reason, we will evaluate existing implementations of the algorithm. We will also simplify the duality of the description of the algorithm in the remainder of this section.
- The suggested utility function is quite accurate compared to the utility functions that we could be using in this algorithm. In general, the deeper we go, the less accurate our utility function has to be. For instance, if we could go nine steps deep into the tic-tac-toe game, all we would need to do is award 1 point for a win, 0 for a draw, and -1 point for a loss, given that, in nine steps, the board is complete, and we have all of the necessary information to make the evaluation. If we could only look four steps deep, this utility function would be completely useless at the start of the game because we need at least five steps to win the game.
- The Minmax algorithm could be optimized further by pruning the tree. Pruning is an act where we get rid of branches that do not contribute to the result. By eliminating unnecessary computations, we save precious resources that could be used to go deeper into the tree.
Optimizing the Minmax Algorithm with Alpha-Beta Pruning
The last consideration in the previous thought process primed us to explore possible optimizations by reducing the search space by focusing our attention on nodes that matter.
There are a few constellations of nodes in the tree where we can be sure that the evaluation of a subtree does not contribute to the end result. We will find, examine, and generalize these constellations to optimize the Minmax algorithm.
Let's examine pruning through the previous example of nodes:
Figure 1.27: Search tree demonstrating pruning nodes
After computing the nodes with values 101, 23, and 110, we can conclude that two levels above, the value 101 will be chosen. Why?
- Suppose X <= 110. Here, the maximum of 110 and X will be chosen, which is 110, and X will be omitted.
- Suppose X > 110. Here, the maximum of 110 and X is X. One level above, the algorithm will choose the lowest value out of the two. The minimum of 101 and X will always be 101, because X > 110. Therefore, X will be omitted a level above.
This is how we prune the tree.
On the right-hand side, suppose we computed branches 10 and 21. Their maximum is 21. The implication of computing these values is that we can omit the computation of nodes Y1, Y2, and Y3, and we know that the value of Y4 is less than or equal to 21. Why?
The minimum of 21 and Y3 is never greater than 21. Therefore, Y4 will never be greater than 21.
We can now choose between a node with utility 101 and another node with a maximal utility of 21. It is obvious that we have to choose the node with utility 101:
Figure 1.28: Example of pruning a tree
This is the idea behind alpha-beta pruning. We prune subtrees that we know are not going to be needed.
Let's see how we can implement alpha-beta pruning in the Minmax algorithm.
First, we will add an alpha and a beta argument to the argument list of Minmax:
def min_max(state, depth, is_maximizing, alpha, beta):
if depth == 0 or is_end_state(state):
return utility(state)
if is_maximizing:
utility = 0
for s in successors(state):
score = MinMax(s, depth - 1, false, alpha, beta)
utility = max(utility, score)
alpha = max(alpha, score)
if beta <= alpha:
break
return utility
else:
utility = infinity
for s in successors(state):
score = MinMax(s, depth - 1, true, alpha, beta)
utility = min(utility, score)
return utility
In the preceding code snippet, we added the alpha and beta arguments to the MinMax function in order to calculate the new alpha score as being the maximum between alpha and beta in the maximizing branch.
Now, we need to do the same with the minimizing branch:
def min_max(state, depth, is_maximizing, alpha, beta):
if depth == 0 or is_end_state( state ):
return utility(state)
if is_maximizing:
utility = 0
for s in successors(state):
score = min_max(s, depth - 1, false, alpha, beta)
utility = max(utility, score)
alpha = max(alpha, score)
if beta <= alpha: break
return utility
else:
utility = infinity
for s in successors(state):
score = min_max(s, depth - 1, true, alpha, beta)
utility = min(utility, score)
beta = min(beta, score)
if beta <= alpha: break
return utility
In the preceding code snippet, we added the new beta score in the else branch, which is the minimum between alpha and beta in the minimizing branch.
We are done with the implementation. It is recommended that you mentally execute the algorithm on our example tree step by step to get a feel for the implementation.
One important piece is missing that has prevented us from doing the execution properly: the initial values for alpha and beta. Any number that is outside the possible range of utility values will do. We will use positive and negative infinity as initial values to call the Minmax algorithm:
alpha = infinity
beta = -infinity
In the next section, we will look at the DRYing technique while using the NegaMax algorithm.
DRYing Up the Minmax Algorithm – the NegaMax Algorithm
The Minmax algorithm works great, especially with alpha-beta pruning. The only problem is that we have if and else branches in the algorithm that essentially negates each other.
As we know, in computer science, there is DRY code and WET code. DRY stands for Don't Repeat Yourself. WET stands for Write Everything Twice. When we write the same code twice, we double our chance of making a mistake while writing it. We also double our chances of each maintenance effort being executed in the future. Hence, it is better to reuse our code.
When implementing the Minmax algorithm, we always compute the utility of a node from the perspective of the AI player. This is why we have to have a utility-maximizing branch and a utility-minimizing branch in the implementations that are dual in nature. As we prefer clean code that describes the problem only once, we could get rid of this duality by changing the point of view of the evaluation.
Whenever the AI player's turn comes, nothing changes in the algorithm.
Whenever the opponent's turn comes, we negate the perspective. Minimizing the AI player's utility is equivalent to maximizing the opponent's utility.
This simplifies the Minmax algorithm:
def Negamax(state, depth, is_players_point_of_view):
if depth == 0 or is_end_state(state):
return utility(state, is_players_point_of_view)
utility = 0
for s in successors(state):
score = Negamax(s,depth-1,not is_players_point_of_view)
return score
There are necessary conditions for using the NegaMax algorithm; for instance, the evaluation of the board state has to be symmetric. If a game state is worth +20 from the first player's perspective, it is worth -20 from the second player's perspective. Therefore, we often normalize the scores around zero.
Using the EasyAI Library
We have already looked at the simpleai library, which helped us execute searches on pathfinding problems. Now, we will use the EasyAI library, which can easily handle an AI search on two-player games, reducing the implementation of the tic-tac-toe problem to writing a few functions on scoring the utility of a board and determining when the game ends.
To install EasyAI, type the following command in Jupyter Notebook:
!pip install easyAI
Note
You can read the documentation of the library on GitHub at https://github.com/Zulko/easyAI.
Activity 1.04: Connect Four
In this activity, we will practice using the EasyAI library and develop a heuristic. We will be using the game Connect Four for this. The game board is seven cells wide and seven cells high. When you make a move, you can only select the column in which you drop your token. Then, gravity pulls the token down to the lowest possible empty cell. Your objective is to connect four of your own tokens horizontally, vertically, or diagonally, before your opponent does, or you run out of empty spaces.
Note
The rules of the game can be found at https://en.wikipedia.org/wiki/Connect_Four.
- Open a new Jupyter Notebook file.
- Write the init method to generate all the possible winning combinations in the game and save them for future use.
- Write a function to enumerate all the possible moves. Then, for each column, check whether there is an unoccupied field. If there is one, make the column a possible move.
- Create a function to make a move (it will be similar to the possible move function), and then check the column of the move and find the first empty cell, starting from the bottom.
- Reuse the lose function from the tic-tac-toe example.
- Implement the show method that prints the board and try out the game.
Note
The solution to this activity can be found on page 330.
The expected output is this:
Figure 1.29: Expected output for the game Connect Four
Summary
In this chapter, we have seen how AI can be used to enhance or substitute human abilities such as to listen, speak, understand language, store and retrieve information, think, see, and move.
Then, we moved on to learning about intelligent agents and the way they interact with the environment, solving a problem in a seemingly intelligent way to pursue a goal.
Then, we introduced Python and learned about its role in AI. We looked at a few important Python libraries for developing AI and prepared data for the intelligent agents. We then created a tic-tac-toe game based on predefined rules. We quantified these rules into a number, a process that we call heuristics. We learned how to use heuristics in the A* search algorithm to find an optimal solution to a problem.
Finally, we got to know about the Minmax and NegaMax algorithms so that the AI could win two-player games. In the next chapter, you will be introduced to regression.