AI with Python – Gaming

AI with Python – Crafting Intelligent Game Agents

Games, at their core, are about strategy. Whether it’s a board game, a video game, or a sports match, players or teams devise strategies before starting and adapt them based on the evolving game state. AI in gaming aims to create non-player characters (NPCs) or opponents that exhibit intelligent behavior, making games more engaging and challenging.

Classic Search Algorithms in Game AI

Many traditional game AI systems rely on search algorithms. These algorithms explore possible future game states to determine the best move.

How They Work

The objective of these search algorithms is to find an optimal sequence of moves leading to a win or a high-value game state. They use the game’s rules and winning conditions to evaluate moves.

Imagine a game as a tree, where the current state is the root node. Each branch represents a possible move, leading to a new game state (node). Search algorithms traverse this tree, analyzing potential outcomes to make informed decisions. Each node can be assigned a score (heuristic value) representing its desirability.

Combinatorial Search and Heuristics

A major challenge with basic search algorithms is that they can be exhaustive, exploring the entire search space. For complex games, this is computationally infeasible, leading to a ‘combinatorial explosion’ of possible states. This is where heuristics come in.

Combinatorial search, guided by heuristics, aims to prune the search space. A heuristic is an educated guess or a rule of thumb that estimates the value of a game state or the promise of a particular move, allowing the AI to focus on more promising branches of the game tree and save resources. Some algorithms that use heuristics include:

Minimax Algorithm

Minimax is a fundamental decision-making algorithm for two-player, zero-sum games (where one player’s gain is the other’s loss). It operates on the principle that each player tries to maximize their own score while assuming the opponent will try to minimize it (maximize their own score, which is the negative of the first player’s).

The algorithm explores the game tree down to a certain depth. At each level, it alternates between maximizing (for the AI’s turn) and minimizing (for the opponent’s turn) the heuristic evaluation of game states. The heuristic function assigns a score to terminal or depth-limited game states, indicating how good that state is for the current player.

Alpha-Beta Pruning

Minimax can still explore many irrelevant branches. Alpha-Beta Pruning is an optimization technique for the Minimax algorithm that significantly reduces the number of nodes evaluated in the search tree.

It works by maintaining two values: Alpha (the best score found so far for the maximizing player on the path to the root) and Beta (the best score found so far for the minimizing player on the path to the root). If a move is found to be worse than a previously explored move for either player, that branch of the tree can be ‘pruned’ (ignored), as it won’t lead to a better overall outcome.

Negamax Algorithm

The Negamax algorithm is a variant of Minimax that simplifies the implementation, especially for games where the heuristic evaluation is always from the perspective of the current player to move. Instead of having separate maximizing and minimizing functions, Negamax uses the observation that max(a, b) = -min(-a, -b).

This means the algorithm can always maximize the negative of the opponent’s score. It often leads to more concise code as it doesn’t need to switch between min and max logic explicitly based on whose turn it is.

Beyond Classic Search: MCTS and Reinforcement Learning

While classic search algorithms are foundational, modern game AI often employs more advanced techniques:

• Monte Carlo Tree Search (MCTS): Effective for games with large branching factors (e.g., Go, complex strategy games). MCTS builds a search tree using random simulations to estimate the value of moves.
• Reinforcement Learning (RL): Agents learn optimal strategies by interacting with the game environment and receiving rewards or penalties for their actions. Deep Reinforcement Learning (e.g., DQN, AlphaZero) combines RL with deep neural networks to tackle highly complex games.

For learning these advanced topics, environments like OpenAI Gym provide excellent platforms.

Building Simple Game Bots with easyAI

For beginners learning game AI principles, the easyAI library offers a straightforward framework for creating AI for two-player games. It abstracts some of the complexities of game tree search. You can install it using pip:

pip install easyAI

Note: easyAI is excellent for educational purposes and simple games. For commercial or highly complex games, more robust engines and algorithms (like MCTS or RL) are typically used.

Example: A Bot for ‘Last Coin Standing’

In this game, players take turns removing coins from a pile. The player forced to take the last coin loses (or, alternatively, wins, depending on the rules; here, avoids taking the last coin). We’ll use easyAI’s TwoPlayersGame class.

First, import necessary components from easyAI:

from easyAI import TwoPlayerGame, Human_Player, AI_Player, Negamax
from easyAI.AI import id_solve # For iterative deepening solve

Define the game class, inheriting from TwoPlayerGame:

class LastCoinStanding(TwoPlayerGame):
    """ In this game, there's a pile of N coins. Players take 1 to K coins.
        The player who avoids taking the last coin wins. """
    def __init__(self, players, num_coins=15, max_coins_per_turn=4):
        self.players = players
        self.num_coins = num_coins
        self.max_coins_per_turn = max_coins_per_turn
        self.nplayer = 1  # Player 1 starts

    def possible_moves(self):
        # A player can take 1 to max_coins_per_turn, but not more than remaining coins
        return [str(i) for i in range(1, min(self.max_coins_per_turn, self.num_coins) + 1)]

    def make_move(self, move):
        self.num_coins -= int(move)

    def win(self):
        # The player who makes num_coins <= 0 makes the opponent take the last coin (or no coin)
        # So, the current player wins if they leave 0 or less coins for the opponent effectively.
        # In easyAI, win() is called AFTER the move. So if num_coins is 0 or less, current player won.
        return self.num_coins <= 0

    def is_over(self):
        return self.win()

    def scoring(self):
        # The player who wins gets 100, loser gets -100 (or 0 if not zero-sum by default)
        return 100 if self.win() else 0

    def show(self):
        print(f"{self.num_coins} coins left in the pile")

    # For transposition table (memoization to speed up search)
    # ttentry gives a unique representation of the game state
    def ttentry(self):
        return self.num_coins

Setting up and running the game:

# Define the AI algorithm (Negamax with a search depth of 5)
ai_algo = Negamax(5)

# To solve the game (find optimal strategy if possible)
# r: result (1 for win, 0 for draw, -1 for loss for player 1)
# d: depth at which solution found
# m: optimal move for player 1 at the start
# This can take time for larger games.
# print("Solving game...")
# r, d, m = id_solve(LastCoinStanding, range(2, 20), win_score=100)
# print(f"Result: {r}, Depth: {d}, Optimal Move: {m}")

# Play the game: AI vs Human
if __name__ == "__main__":
    game = LastCoinStanding([AI_Player(ai_algo), Human_Player()])
    game.play()

When you run this, easyAI will manage the game flow. The output will show the game progression, for example:

15 coins left in the pile
Move #1: player 1 (AI) plays 4:
11 coins left in the pile
Player 2 (Human) what do you play? 2
Move #2: player 2 plays 2:
9 coins left in the pile
Move #3: player 1 (AI) plays 3:
6 coins left in the pile
Player 2 (Human) what do you play? 1
Move #4: player 2 plays 1:
5 coins left in the pile
Move #5: player 1 (AI) plays 4:
1 coins left in the pile
Player 2 (Human) what do you play? 1
Move #6: player 2 plays 1:
0 coins left in the pile
Player 2 (Human) wins!

Note: The original example’s win_game was slightly different. In easyAI, win() should return true if the player whose turn just ended made a winning move. The scoring function then determines the game’s outcome score. The id_solve output (e.g., d:2, a:0, m:1) indicates depth, score, and move; this is specific to easyAI’s solver output format.

Example: A Bot for Tic-Tac-Toe

Tic-Tac-Toe is a classic game perfect for illustrating game AI. Here’s how to implement it with easyAI:

Imports:

from easyAI import TwoPlayerGame, AI_Player, Negamax
from easyAI.Player import Human_Player

Game Class Definition:

class TicTacToe(TwoPlayerGame):
    """ The classic game of Tic-Tac-Toe. """
    def __init__(self, players):
        self.players = players
        self.board = [0] * 9  # 0: empty, 1: player 1 (O), 2: player 2 (X)
        self.nplayer = 1  # Player 1 starts

    def possible_moves(self):
        return [i + 1 for i, e in enumerate(self.board) if e == 0]

    def make_move(self, move):
        self.board[int(move) - 1] = self.nplayer

    def unmake_move(self, move): # Optional, for AI search
        self.board[int(move) - 1] = 0

    def lose(self):
        """ Returns True if the current player has lost. """
        # Check if opponent (self.nopponent) has three in a row
        winning_combinations = [
            [0, 1, 2], [3, 4, 5], [6, 7, 8],  # Rows
            [0, 3, 6], [1, 4, 7], [2, 5, 8],  # Columns
            [0, 4, 8], [2, 4, 6]             # Diagonals
        ]
        return any(
            all(self.board[c] == self.nopponent for c in combo)
            for combo in winning_combinations
        )

    def is_over(self):
        # Game is over if someone has lost or if there are no more moves (draw)
        return self.lose() or (self.possible_moves() == [])

    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)
        ]))

    def scoring(self):
        # Returns 100 if current player wins, -100 if opponent wins (current player loses), 0 for draw
        return -100 if self.lose() else 0

    # For transposition table
    def ttentry(self):
        return tuple(self.board) # Tuple of board state is a good unique key

Running the Tic-Tac-Toe game:

# AI algorithm: Negamax with search depth 7 (Tic-Tac-Toe is small enough to solve)
# Higher depth means stronger AI but more computation time.
if __name__ == "__main__":
    ai_algo_ttt = Negamax(7)
    game_ttt = TicTacToe([Human_Player(), AI_Player(ai_algo_ttt)]) # Human (O) vs AI (X)
    # game_ttt = TicTacToe([AI_Player(ai_algo_ttt), Human_Player()]) # AI (O) vs Human (X)
    game_ttt.play()

An example game session might look like this (Player 1 is Human ‘O’, Player 2 is AI ‘X’):

. . .
. . .
. . .
Player 1 what do you play? 1
Move #1: player 1 plays 1:
O . .
. . .
. . .
Move #2: player 2 (AI) plays 5:
O . .
. X .
. . .
Player 1 what do you play? 3
Move #3: player 1 plays 3:
O . O
. X .
. . .
Move #4: player 2 (AI) plays 2:
O X O
. X .
. . .
Player 1 what do you play? 7
Move #5: player 1 plays 7:
O X O
. X .
O . .
Move #6: player 2 (AI) plays 4:
O X O
X X .
O . .
Player 1 what do you play? 6
Move #7: player 1 plays 6:
O X O
X X O
O . .
Move #8: player 2 (AI) plays 9:
O X O
X X O
O . X
Player 1 what do you play? 8
Move #9: player 1 plays 8:
O X O
X X O
O O X
Game over. It's a draw!