Download our e-book of Introduction To Python
Related Blog
Matplotlib - Subplot2grid() FunctionDiscuss Microsoft Cognitive ToolkitMatplotlib - Working with ImagesMatplotlib - PyLab moduleMatplotlib - Working With TextMatplotlib - Setting Ticks and Tick LabelsCNTK - Creating First Neural NetworkMatplotlib - MultiplotsMatplotlib - Quiver PlotPython - Chunks and Chinks View More
Top Discussion
How can I write Python code to change a date string from "mm/dd/yy hh: mm" format to "YYYY-MM-DD HH: mm" format? Which sorting technique is used by sort() and sorted() functions of python? How to use Enum in python? Can you please help me with this error? I was just selecting some random columns from the diabetes dataset of sklearn. Decision tree is a classification algo...How can it be applied to load diabetes dataset which has DV continuous Objects in Python are mutable or immutable? How can unclassified data in a dataset be effectively managed when utilizing a decision tree-based classification model in Python? How to leave/exit/deactivate a Python virtualenvironment Join Discussion
Top Courses
Webinars
AI with Python – Gaming
Jon Wood
2 years ago
Table of Contents
- Search Algorithms
1. How it works
2. Combinational Search
3. Minimax Algorithm
4. Alpha-Beta Pruning
5. Negamax Algorithm
- Building Bots to Play Games
1. A Bot to Play Last Coin Standing
2. A Bot to Play Tic Tac Toe
Games are played with a strategy. Every player or team would make a strategy before starting the game and they have to change or build a new strategy according to the current situation(s) in the game.
Search Algorithms
You will have to consider computer games also with the same strategy as above. Note that Search Algorithms are the ones that figure out the strategy in computer games.
1. How it works?
The goal of search algorithms is to find the optimal set of moves so that they can reach at the final destination and win. These algorithms use the winning set of conditions, different for every game, to find the best moves.
Visualize a computer game as the tree. We know that tree has nodes. Starting from the root, we can come to the final winning node, but with optimal moves. That is the work of search algorithms. Every node in such tree represents a future state. The search algorithms search through this tree to make decisions at each step or node of the game.
2. Combinational Search
The major disadvantage of using search algorithms is that they are exhaustive in nature, which is why they explore the entire search space to find the solution that leads to wastage of resources. It would be more cumbersome if these algorithms need to search the whole search space for finding the final solution.
To eliminate such kind of problem, we can use combinational search which uses the heuristic to explore the search space and reduces its size by eliminating the possible wrong moves. Hence, such algorithms can save the resources. Some of the algorithms that use heuristic to search the space and save the resources are discussed here −
3. Minimax Algorithm
It is the strategy used by combinational search that uses heuristic to speed up the search strategy. The concept of Minimax strategy can be understood with the example of two player games, in which each player tries to predict the next move of the opponent and tries to minimize that function. Also, in order to win, the player always try to maximize its own function based on the current situation.
Heuristic plays an important role in such kind of strategies like Minimax. Every node of the tree would have a heuristic function associated with it. Based on that heuristic, it will take the decision to make a move towards the node that would benefit them the most.
4. Alpha-Beta Pruning
A major issue with Minimax algorithm is that it can explore those parts of the tree that are irrelevant, leads to the wastage of resources. Hence there must be a strategy to decide which part of the tree is relevant and which is irrelevant and leave the irrelevant part unexplored. Alpha-Beta pruning is one such kind of strategy.
The main goal of Alpha-Beta pruning algorithm is to avoid the searching those parts of the tree that do not have any solution. The main concept of Alpha-Beta pruning is to use two bounds named Alpha, the maximum lower bound, and Beta, the minimum upper bound. These two parameters are the values that restrict the set of possible solutions. It compares the value of the current node with the value of alpha and beta parameters, so that it can move to the part of the tree that has the solution and discard the rest.
5. Negamax Algorithm
This algorithm is not different from Minimax algorithm, but it has a more elegant implementation. The main disadvantage of using Minimax algorithm is that we need to define two different heuristic functions. The connection between these heuristic is that, the better a state of a game is for one player, the worse it is for the other player. In Negamax algorithm, the same work of two heuristic functions is done with the help of a single heuristic function.
Building Bots to Play Games
For building bots to play two-player games in AI, we need to install the easyAI library. It is an artificial intelligence framework that provides all the functionality to build two-player games. You can download it with the help of the following command −
pip install easyAI
1. A Bot to Play Last Coin Standing
In this game, there would be a pile of coins. Each player has to take a number of coins from that pile. The goal of the game is to avoid taking the last coin in the pile. We will be using the class LastCoinStanding inherited from the TwoPlayersGame class of the easyAI library. The following code shows the Python code for this game −
Import the required packages as shown −
from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player
from easyAI.AI import TTNow, inherit the class from the TwoPlayerGame class to handle all operations of the game −
class LastCoin_game(TwoPlayersGame):
#Now, define the players and the player who is going to start the game.
self.players = players
self.nplayer = 1
#Now, define the number of coins in the game, here we are using 15 coins for the game.
self.num_coins = 15
#Define the maximum number of coins a player can take in a movie.
self.max_coins = 4
#Now there are some certain things to define as shown in the following code. Define possible moves.
def possible_moves(self):
return [str(a) for a in range(1, self.max_coins + 1)]
#Define the removal of the coins
def make_move(self, move):
self.num_coins -= int(move)
#Define who took the last coin.
def win_game(self):
return self.num_coins <= 0
#Define when to stop the game, that is when somebody wins.
def is_over(self):
return self.win()
#Define how to compute the score.
def score(self):
return 100 if self.win_game() else 0
#Define the number of coins remaining in the pile.
def show(self):
print(self.num_coins, 'coins left in the pile')
if __name__ == "__main__":
tt = TT()
LastCoin_game.ttentry = lambda self: self.num_coinsSolving the game with the following code block −
r, d, m = id_solve(LastCoin_game,
range(2, 20), win_score=100, tt=tt)
print(r, d, m)Deciding who will start the game
game = LastCoin_game([AI_Player(tt), Human_Player()])
game.play()You can find the following output and a simple play of this game −
d:2, a:0, m:1
d:3, a:0, m:1
d:4, a:0, m:1
d:5, a:0, m:1
d:6, a:100, m:4
1 6 4
15 coins left in the pile
Move #1: player 1 plays 4 :
11 coins left in the pile
Player 2 what do you play ? 2
Move #2: player 2 plays 2 :
9 coins left in the pile
Move #3: player 1 plays 3 :
6 coins left in the pile
Player 2 what do you play ? 1
Move #4: player 2 plays 1 :
5 coins left in the pile
Move #5: player 1 plays 4 :
1 coins left in the pile
Player 2 what do you play ? 1
Move #6: player 2 plays 1 :
0 coins left in the pile2. A Bot to Play Tic Tac Toe
Tic-Tac-Toe is very familiar and one of the most popular games. Let us create this game by using the easyAI library in Python. The following code is the Python code of this game −
Import the packages as shown −
from easyAI import TwoPlayersGame, AI_Player, Negamax
from easyAI.Player import Human_PlayerInherit the class from the TwoPlayerGame class to handle all operations of the game −
class TicTacToe_game(TwoPlayersGame):
def __init__(self, players):
#Now, define the players and the player who is going to start the game −
self.players = players
self.nplayer = 1
#Define the type of board −
self.board = [0] * 9
#Now there are some certain things to define as follows −
#Define possible moves
def possible_moves(self):
return [x + 1 for x, y in enumerate(self.board) if y == 0]
#Define the move of a player −
def make_move(self, move):
self.board[int(move) - 1] = self.nplayer
#To boost AI, define when a player makes a move −
def umake_move(self, move):
self.board[int(move) - 1] = 0Define the loose condition that an opponent has three in a line
def condition_for_lose(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[z-1] == self.nopponent)
for z in combination]) for combination in possible_combinations])Define a check for the finish of the game
def is_over(self):
return (self.possible_moves() == []) or self.condition_for_lose()Show the current position of the players in the game
def show(self):
print('\n'+'\n'.join([' '.join([['.', 'O', 'X'][self.board[3*j + i]]
for i in range(3)]) for j in range(3)]))Compute the scores.
def scoring(self):
return -100 if self.condition_for_lose() else 0Define the main method to define the algorithm and start the game −
if __name__ == "__main__":
algo = Negamax(7)
TicTacToe_game([Human_Player(), AI_Player(algo)]).play()You can see the following output and a simple play of this game −
. . .
. . .
. . .
Player 1 what do you play ? 1
Move #1: player 1 plays 1 :
O . .
. . .
. . .
Move #2: player 2 plays 5 :
O . .
. X .
121
. . .
Player 1 what do you play ? 3
Move #3: player 1 plays 3 :
O . O
. X .
. . .
Move #4: player 2 plays 2 :
O X O
. X .
. . .
Player 1 what do you play ? 4
Move #5: player 1 plays 4 :
O X O
O X .
. . .
Move #6: player 2 plays 8 :
O X O
O X .
. X .Like the Blog, then Share it with your friends and colleagues to make this AI community stronger.
To learn more about nuances of Artificial Intelligence, Python Programming, Deep Learning, Data Science and Machine Learning, visit our blog page - https://insideaiml.com/blog
Keep Learning. Keep Growing.