Building Games With Artificial IntelligenceSearch algorithms are used in games to figure out a strategy.
The algorithms search through the possibilities and pick the best move.
DammnnBlockedUnblockFollowFollowingMay 9google.
com/imagesThere are various parameters to think about — speed, accuracy, complexity, and so on.
These algorithms consider all possible actions available at this time and then evaluate their future moves based on these options.
The goal of these algorithms is to find the optimal set of moves that will help them arrive at the final condition.
Every game has a different set of winning conditions.
These algorithms use those conditions to find the set of moves.
The description given in the previous paragraph is ideal if there is no opposing player.
Things are not as straightforward with games that have multiple players.
Let’s consider a two-player game.
For every move made by a player, the opposing player will make a move to prevent the player from achieving the goal.
So when a search algorithm finds the optimal set of moves from the current state, it cannot just go ahead and make those moves because the opposing player will stop it.
This basically means that search algorithms need to constantly re-evaluate after each move.
Let’s discuss how a computer perceives any given game.
We can think of a game as a search tree.
Each node in this tree represents a future state.
For example, if you are playing Tic-Tac-Toe (Noughts and Crosses), you can construct this tree to represent all possible moves.
We start from the root of the tree, which is the starting point of the game.
This node will have several children that represent various possible moves.
Those children, in turn, will have more children that represent game states after more moves by the opponent.
The terminal nodes of the tree represent the final results of the game after making various moves.
The game would either end in a draw or one of the players would win it.
The search algorithms search through this tree to make decisions at each step of the game.
Combinatorial searchSearch algorithms appear to solve the problem of adding intelligence to games, but there’s a drawback.
These algorithms employ a type of search called exhaustive search, which is also known as a brute force search.
It basically explores the entire search space and tests every possible solution.
It means that, in the worst case, we will have to explore all the possible solutions before we get the right solution.
As the games get more complex, we cannot rely on brute force search because the number of possibilities gets enormous.
This quickly becomes computationally intractable.
In order to solve this problem, we use a combinatorial search to solve problems.
It refers to a field of study where search algorithms efficiently explore the solution space using heuristics or by reducing the size of the search space.
This is very useful in games like Chess or Go.
Combinatorial search works efficiently by using pruning strategies.
These strategies help it avoid testing all possible solutions by eliminating the ones that are obviously wrong.
This helps save time and effort.
Minimax algorithmNow that we have briefly discussed combinatorial search, let’s talk about the heuristics that are employed by combinatorial search algorithms.
These heuristics are used to speed up the search strategy and the Minimax algorithm is one such strategy used by combinatorial search.
When two players are playing against each other, they are basically working towards opposite goals.
So each side needs to predict what the opposing player is going to do in order to win the game.
Keeping this in mind, Minimax tries to achieve this through strategy.
It will try to minimize the function that the opponent is trying to maximize.
As we know, brute forcing the solution is not an option.
The computer cannot go through all the possible states and then get the best possible set of moves to win the game.
The computer can only optimize the moves based on the current state using a heuristic.
The computer constructs a tree and it starts from the bottom.
It evaluates which moves would benefit its opponent.
Basically, it knows which moves the opponent is going to make based on the premise that the opponent will make the moves that would benefit them the most, and thereby be of the least benefit to the computer.
This outcome is one of the terminal nodes of the tree and the computer uses this position to work backwards.
Each option that’s available to the computer can be assigned a value and it can then pick the highest value to take an action.
Alpha-Beta pruningMinimax search is an efficient strategy, but it still ends up exploring parts of the tree that are irrelevant.
Let’s consider a tree where we are supposed to search for solutions.
Once we find an indicator on a node that tells us that the solution does not exist in that sub-tree, there is no need to evaluate that sub-tree.
But Minimax search is a bit too conservative, so it ends up exploring that sub-tree.
We need to be smart about it and avoid searching a part of a tree that is not necessary.
This process is called pruning and Alpha-Beta pruning is a type of avoidance strategy that is used to avoid searching parts of the tree that do not contain the solution.
The Alpha and Beta parameters in alpha-beta pruning refer to the two bounds that are used during the calculation.
These parameters refer to the values that restrict the set of possible solutions.
This is based on the section of the tree that has already been explored.
Alpha is the maximum lower bound of the number of possible solutions and Beta is the minimum upper bound on the number of possible solutions.
As we discussed earlier, each node can be assigned a value based on the current state.
When the algorithm considers any new node as a potential path to the solution, it can work out if the current estimate of the value of the node lies between alpha and beta.
This is how it prunes the search.
Negamax algorithmThe Negamax algorithm is a variant of Minimax that’s frequently used in real world implementations.
A two-player game is usually a zero-sum game, which means that one player’s loss is equal to another player’s gain and vice versa.
Negamax uses this property extensively to come up with a strategy to increases its chances of winning the game.
In terms of the game, the value of a given position to the first player is the negation of the value to the second player.
Each player looks for a move that will maximize the damage to the opponent.
The value resulting from the move should be such that the opponent gets the least value.
This works both ways seamlessly, which means that a single method can be used to value the positions.
This is where it has an advantage over Minimax in terms of simplicity.
Minimax requires that the first player select the move with the maximum value, whereas the second player must select a move with the minimum value.
Alpha-beta pruning is used here as well.
Building a bot to play Last Coin StandingThis is a game where we have a pile of coins and each player takes turns to take a number of coins from the pile.
There is a lower and an upper bound on the number of coins that can be taken from the pile.
The goal of the game is to avoid taking the last coin in the pile.
This recipe is a variant of the Game of Bones recipe given in the easyAI library.
Let's see how to build a game where the computer can play against the user.
Create a new Python file and import the following packages:from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player from easyAI.
AI import TTCreate a class to handle all the operations of the game.
We will be inheriting from the base class TwoPlayersGame available in the easyAI library.
There are a couple of parameters that have been to defined in order for it to function properly.
The first one is the players variable.
We will talk about the player object later.
Create the class using the following code:class LastCoinStanding(TwoPlayersGame): def __init__(self, players): # Define the players.
Necessary parameter.
self.
players = playersDefine who is going to start the game.
The players are numbered from one.
So in this case, player one starts the game:# Define who starts the game.
Necessary parameter.
self.
nplayer = 1Define the number of coins in the pile.
You are free to choose any number here.
In this case, let’s choose 25:# Overall number of coins in the pile self.
num_coins = 25Define the maximum number of coins that can be taken out in any move.
You are free to choose any number for this parameter as well.
Let’s choose 4 in our case:# Define max number of coins per move self.
max_coins = 4Define all the possible movies.
In this case, players can take either 1, 2, 3, or 4 coins in each move:# Define possible moves def possible_moves(self): return [str(x) for x in range(1, self.
max_coins + 1)]Define a method to remove the coins and keep track of the number of coins remaining in the pile:# Remove coins def make_move(self, move): self.
num_coins -= int(move)Check if somebody won the game by checking the number of coins remaining:# Did the opponent take the last coin?.def win(self): return self.
num_coins <= 0Stop the game after somebody wins it:# Stop the game when somebody wins def is_over(self): return self.
win()Compute the score based on the win method.
It's necessary to define this method:# Compute score def scoring(self): return 100 if self.
win() else 0Define a method to show the current status of the pile:# Show number of coins remaining in the pile def show(self): print(self.
num_coins, 'coins left in the pile')Define the main function and start by defining the transposition table.
Transposition tables are used in games to store the positions and movements so as to speed up the algorithm.
Type in the following code:if __name__ == "__main__": # Define the transposition table tt = TT()Define the method ttentry to get the number of coins.
It's an optional method that's used to create a string to describe the game:# Define the method LastCoinStanding.
ttentry = lambda self: self.
num_coinsLet’s solve the game using AI.
The function id_solve is used to solve a given game using iterative deepening.
It basically determines who can win a game using all the paths.
It looks to answer questions such as, Can the first player force a win by playing perfectly?.Will the computer always lose against a perfect opponent?The method id_solve explores various options in the game's Negamax algorithm several times.
It always starts at the initial state of the game and takes increasing depth to keep going.
It will do it until the score indicates that somebody will win or lose.
The second argument in the method takes a list of depths that it will try out.
In this case, it will try all the values from 2 to 20:# Solve the game result, depth, move = id_solve(LastCoinStanding, range(2, 20), win_score=100, tt=tt) print(result, depth, move)Start the game against the computer:# Start the game game = LastCoinStanding([AI_Player(tt), Human_Player()]) game.
play()The full code is given in the file coins.
py.
It's an interactive program, so it will expect input from the user.
If you run the code, you will basically be playing against the computer.
Your goal is to force the computer to take the last coin, so that you win the game.
If you run the code, you will get the following output on your Terminal at the beginning:If you scroll down, you will see the following towards the end:As we can see, the computer wins the game because the user picked up the last coin.
Building a bot to play Tic-Tac-ToeTic-Tac-Toe (Noughts and Crosses) is probably one of the most famous games.
Let’s see how to build a game where the computer can play against the user.
This is a minor variant of the Tic-Tac-Toe recipe given in the easyAI library.
Create a new Python file and import the following packages:from easyAI import TwoPlayersGame, AI_Player, Negamax from easyAI.
Player import Human_PlayerDefine a class that contains all the methods to play the game.
Start by defining the players and who starts the game:class GameController(TwoPlayersGame): def __init__(self, players): # Define the players self.
players = players # Define who starts the game self.
nplayer = 1We will be using a 3×3 board numbered from one to nine row-wise:# Define the board self.
board = [0] * 9Define a method to compute all the possible moves:# Define possible moves def possible_moves(self): return [a + 1 for a, b in enumerate(self.
board) if b == 0]Define a method to update the board after making a move:# Make a move def make_move(self, move): self.
board[int(move) – 1] = self.
nplayerDefine a method to see if somebody has lost the game.
We will be checking if somebody has three in a row:# Does the opponent have three in a line?.def loss_condition(self): possible_combinations = [[1,2,3], [4,5,6], [7,8,9], [1,4,7], [2,5,8], [3,6,9], [1,5,9], [3,5,7]] return any([all([(self.
board[i-1] == self.
nopponent) for i in combination]) for combination in possible_combinations])Check if the game is over using the loss_condition method:# Check if the game is over def is_over(self): return (self.
possible_moves() == []) or self.
loss_condition()Define a method to show the current progress:# Show current position def show(self): print('.'+'.'.
join([' '.
join([['.
', 'O', 'X'][self.
board[3*j + i]] for i in range(3)]) for j in range(3)]))Compute the score using the loss_condition method:# Compute the score def scoring(self): return -100 if self.
loss_condition() else 0Define the main function and start by defining the algorithm.
We will be using Negamax as the AI algorithm for this game.
We can specify the number of steps in advance that the algorithm should think.
In this case, let’s choose 7:if __name__ == "__main__": # Define the algorithm algorithm = Negamax(7)Start the game:# Start the game GameController([Human_Player(), AI_Player(algorithm)]).
play()It's an interactive game where you play against the computer.
If you run the code, you will get the following output on your Terminal at the beginning:If you scroll down, you will see the following printed on your Terminal once it finishes executing the code:As we can see, the game ends in a draw.
Building two bots to play Connect Four against each otherConnect Four™ is a popular two-player game sold under the Milton Bradley trademark.
It is also known by other names such as Four in a Row or Four Up.
In this game, the players take turns dropping discs into a vertical grid consisting of six rows and seven columns.
The goal is to get four discs in a line.
This is a variant of the Connect Four recipe given in the easyAI library.
Let’s see how to build it.
In this recipe, instead of playing against the computer, we will create two bots that will play against each other.
We will use a different algorithm for each to see which one wins.
Create a new Python file and import the following packages:import numpy as np from easyAI import TwoPlayersGame, Human_Player, AI_Player, Negamax, SSSDefine a class that contains all the methods needed to play the game:class GameController(TwoPlayersGame): def __init__(self, players, board = None): # Define the players self.
players = playersDefine the board with six rows and seven columns:# Define the configuration of the board self.
board = board if (board != None) else ( np.
array([[0 for i in range(7)] for j in range(6)]))Define who’s going to start the game.
In this case, let’s have player one start the game:# Define who starts the game self.
nplayer = 1Define the positions:# Define the positions self.
pos_dir = np.
array([[[i, 0], [0, 1]] for i in range(6)] + [[[0, i], [1, 0]] for i in range(7)] + [[[i, 0], [1, 1]] for i in range(1, 3)] + [[[0, i], [1, 1]] for i in range(4)] + [[[i, 6], [1, -1]] for i in range(1, 3)] + [[[0, i], [1, -1]] for i in range(3, 7)])Define a method to get all the possible moves:# Define possible moves def possible_moves(self): return [i for i in range(7) if (self.
board[:, i].
min() == 0)]Define a method to control how to make a move:# Define how to make the move def make_move(self, column): line = np.
argmin(self.
board[:, column] != 0) self.
board[line, column] = self.
nplayerDefine a method to show the current status:# Show the current status def show(self): print('.' + '.'.
join( ['0 1 2 3 4 5 6', 13 * '-'] + [' '.
join([['.
', 'O', 'X'][self.
board[5 – j][i]] for i in range(7)]) for j in range(6)]))Define a method to compute what a loss looks like.
Whenever somebody gets four in a line, that player wins the game:# Define what a loss_condition looks like def loss_condition(self): for pos, direction in self.
pos_dir: streak = 0 while (0 <= pos[0] <= 5) and (0 <= pos[1] <= 6): if self.
board[pos[0], pos[1]] == self.
nopponent: streak += 1 if streak == 4: return True else: streak = 0 pos = pos + direction return FalseCheck if the game is over by using the loss_condition method:# Check if the game is over def is_over(self): return (self.
board.
min() > 0) or self.
loss_condition()Compute the score:# Compute the score def scoring(self): return -100 if self.
loss_condition() else 0Define the main function and start by defining the algorithms.
We will let two algorithms play against each other.
We will use Negamax for the first computer player and SSS* algorithm for the second computer player.
SSS* is basically a search algorithm that conducts a state space search by traversing the tree in a best-first style.
Both methods take, as an input argument, the number of turns in advance to think about.
In this case, let’s use five for both:if __name__ == '__main__': # Define the algorithms that will be used algo_neg = Negamax(5) algo_sss = SSS(5)Start playing the game:# Start the game game = GameController([AI_Player(algo_neg), AI_Player(algo_sss)]) game.
play()Print the result:# Print the result if game.
loss_condition(): print('.Player', game.
nopponent, 'wins.
') else: print(".It's a draw.
")This is not an interactive game.
We are just pitting one algorithm against another.
Negamax algorithm is player one and SSS* algorithm is player two.
If you run the code, you will get the following output on your Terminal at the beginning:If you scroll down, you will see the following towards the end:As we can see, player two wins the game.
Building two bots to play Hexapawn against each otherHexapawn is a two-player game where we start with a chessboard of size NxM.
We have pawns on each side of the board and the goal is to advance a pawn all the way to the other end of the board.
The standard pawn rules of chess are applicable here.
This is a variant of the Hexapawn recipe given in the easyAI library.
We will create two bots and pit an algorithm against itself to see what happens.
Create a new Python file and import the following packages:from easyAI import TwoPlayersGame, AI_Player, Human_Player, NegamaxDefine a class that contains all the methods necessary to control the game.
Start by defining the number of pawns on each side and the length of the board.
Create a list of tuples containing the positions:class GameController(TwoPlayersGame): def __init__(self, players, size = (4, 4)): self.
size = size num_pawns, len_board = size p = [[(i, j) for j in range(len_board)] for i in [0, num_pawns – 1]]Assign the direction, goals, and pawns to each player:for i, d, goal, pawns in [(0, 1, num_pawns – 1, p[0]), (1, -1, 0, p[1])]: players[i].
direction = d players[i].
goal_line = goal players[i].
pawns = pawnsDefine the players and specify who starts first:# Define the players self.
players = players # Define who starts first self.
nplayer = 1Define the alphabets that will be used to identify positions like B6 or C7 on a chessboard:# Define the alphabets self.
alphabets = 'ABCDEFGHIJ'Define a lambda function to convert strings to tuples:# Convert B4 to (1, 3) self.
to_tuple = lambda s: (self.
alphabets.
index(s[0]), int(s[1:]) – 1)Define a lambda function to convert tuples to strings:# Convert (1, 3) to B4 self.
to_string = lambda move: ' '.
join([self.
alphabets[ move[i][0]] + str(move[i][1] + 1) for i in (0, 1)])Define a method to compute the possible moves:# Define the possible moves def possible_moves(self): moves = [] opponent_pawns = self.
opponent.
pawns d = self.
player.
directionIf you don’t find an opponent pawn in a position, then that’s a valid move:for i, j in self.
player.
pawns: if (i + d, j) not in opponent_pawns: moves.
append(((i, j), (i + d, j))) if (i + d, j + 1) in opponent_pawns: moves.
append(((i, j), (i + d, j + 1))) if (i + d, j – 1) in opponent_pawns: moves.
append(((i, j), (i + d, j – 1))) return list(map(self.
to_string, [(i, j) for i, j in moves]))Define how to make a move and update the pawns based on that:# Define how to make a move def make_move(self, move): move = list(map(self.
to_tuple, move.
split(' '))) ind = self.
player.
pawns.
index(move[0]) self.
player.
pawns[ind] = move[1] if move[1] in self.
opponent.
pawns: self.
opponent.
pawns.
remove(move[1])Define the conditions for a loss.
If a player gets 4 in a line, then the opponent loses:# Define what a loss looks like def loss_condition(self): return (any([i == self.
opponent.
goal_line for i, j in self.
opponent.
pawns]) or (self.
possible_moves() == []) )Check if the game is over using the loss_condition method:# Check if the game is over def is_over(self): return self.
loss_condition()Print the current status:# Show the current status def show(self): f = lambda x: '1' if x in self.
players[0].
pawns else ( '2' if x in self.
players[1].
pawns else '.
') print(".".
join([" ".
join([f((i, j)) for j in range(self.
size[1])]) for i in range(self.
size[0])]))Define the main function and start by defining the scoring lambda function:if __name__=='__main__': # Compute the score scoring = lambda game: -100 if game.
loss_condition() else 0Define the algorithm to be used.
In this case, we will use Negamax that can calculate 12 moves in advance and uses a scoring lambda function for strategy:# Define the algorithm algorithm = Negamax(12, scoring)Start playing the game:# Start the game game = GameController([AI_Player(algorithm), AI_Player(algorithm)]) game.
play() print('.Player', game.
nopponent, 'wins after', game.
nmove, 'turns')The full code is given in the file hexapawn.
py.
It's not an interactive game.
We are pitting an AI algorithm against itself.
If you run the code, you will get the following output on your Terminal at the beginning:If you scroll down, you will see the following towards the end:As we can see, player one wins the game.
.. More details