井字棋 AI-Python

1. 介绍程序中的算法 ：

MinMax算法，也称为极小化极大算法，是一种在博弈论中广泛应用的算法，用于在两个竞争者之间进行零和博弈时，找出最优策略。

该算法适用于井字棋、象棋等游戏，旨在为玩家提供最佳决策。其基本思想是假设对手不会犯错误，从而在最坏情况下保证自己的最大利益。

Minimax算法的核心在于构建一个博弈树，这个树展示了所有可能的游戏状态和双方的决策路径。每个节点代表一种游戏状态，边代表从一种状态到另一种状态的转换。在这个树中，一方努力最大化自己的收益（MAX节点），而另一方努力最小化对方的收益（MIN节点）。

具体来说，如果当前是MAX节点（即玩家希望最大化收益的节点），它会评估所有可能的走法，并选择能带来最大价值的走法。相反，如果当前是MIN节点（即对手试图最小化玩家收益的节点），则选择对玩家最不利的走法。通过这种递归方式，Minimax算法能够找到一条最优路径，使得在对方采取最佳反应的情况下，自己的损失最小。

然而，这种方法存在明显的效率问题，尤其是当博弈树非常庞大时。为了优化这一过程，引入了Alpha-Beta剪枝技术。这种技术通过维护两个值——Alpha（当前找到的最大下界）和Beta（当前找到的最小上界），在搜索过程中剪枝那些不可能优于已有选择的子树，从而显著减少搜索量。

总的来说，Minimax算法通过构建博弈树并递归评估每个可能的游戏状态，寻找在对手采取最优反应的情况下能够保证的最佳结果。结合Alpha-Beta剪枝，可以有效提高搜索效率，使得该算法在复杂的游戏中依然实用。

2.应用 Minimax 算法：

def minimax(board, depth, is_maximizing, alpha=float('-inf'), beta=float('inf'), depth_limit=None):
    winner = check_winner(board)
    if winner == 'X':
        return 1 / depth
    elif winner == 'O':
        return -1 / depth
    elif is_draw(board):
        return 0

3.源代码：

import time
def check_winner(board):
    # 检查行是否有获胜者
    for row in board:
        if row.count(row[0]) == len(row) and row[0] != ' ':
            return row[0]
    
    # 检查列是否有获胜者
    for col in range(len(board)):
        if all(row[col] == board[0][col] for row in board) and board[0][col] != ' ':
            return board[0][col]
    
    # 检查对角线是否有获胜者
    if all(board[i][i] == board[0][0] for i in range(len(board))) and board[0][0] != ' ':
        return board[0][0]
    if all(board[i][len(board)-1-i] == board[0][len(board)-1] for i in range(len(board))) and board[0][len(board)-1] != ' ':
        return board[0][len(board)-1]
    
    # 检查是否平局
    if all(all(cell != ' ' for cell in row) for row in board):
        return 'draw'
    
    # 没有获胜者且游戏未结束
    return None

def is_draw(board):
    return check_winner(board) == 'draw'
def make_move(board, move, player):
    row, col = move
    new_board = [row[:] for row in board]  # 创建棋盘的深拷贝以避免修改原始棋盘
    new_board[row][col] = player
    return new_board

def get_valid_moves(board):
    valid_moves = []
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == ' ':
                valid_moves.append((i, j))
    return valid_moves

def minimax(board, depth, is_maximizing, alpha=float('-inf'), beta=float('inf'), depth_limit=None):
    winner = check_winner(board)
    if winner == 'X':
        return 1 / depth
    elif winner == 'O':
        return -1 / depth
    elif is_draw(board):
        return 0

    if depth_limit is not None and depth >= depth_limit:
        return 10000  # 返回一个默认评估值，例如 0，表示在这个深度上不进行进一步搜索

    if is_maximizing:
        best_score = float('-inf')
        for move in get_valid_moves(board):
            new_board = make_move(board, move, 'X')
            score = minimax(new_board, depth + 1, False, alpha, beta, depth_limit)
            best_score = max(best_score, score)
            alpha = max(alpha, best_score)
            if beta <= alpha:
                break
        return best_score
    else:
        best_score = float('inf')
        for move in get_valid_moves(board):
            new_board = make_move(board, move, 'O')
            score = minimax(new_board, depth + 1, True, alpha, beta, depth_limit)
            best_score = min(best_score, score)
            beta = min(beta, best_score)
            if beta <= alpha:
                break
        return best_score

def ai_move(board, depth_limit=None):
    best_score = float('-inf')
    best_move = None
    for move in get_valid_moves(board):
        new_board = make_move(board, move, 'X')
        score = minimax(new_board, 1, False, depth_limit=depth_limit)
        if score > best_score:
            best_score = score
            best_move = move
    return best_move

def print_board(board):
    for row in board:
        print(" | ".join(row))
        print("-" * (4 * len(board) - 3))

def main():
    board = [[' ' for _ in range(3)] for _ in range(3)]
    current_player = 'X'
    
    while True:
        print_board(board)
        if current_player == 'X':
            # 玩家输入
            row, col = map(int, input("请输入行和列（用空格分隔）：").split())
            if board[row][col] != ' ':
                print("无效的移动，请重新输入。")
                continue
            board = make_move(board, (row, col), current_player)
        else:
            # AI输入
            print("AI正在思考...")
            time.sleep(1)
            move = ai_move(board, depth_limit=1000)
            board = make_move(board, move, current_player)
        
        winner = check_winner(board)
        if winner is not None:
            print_board(board)
            if winner == 'draw':
                print("平局！")
            else:
                print(f"{winner} 赢了！")
            break
        
        current_player = 'O' if current_player == 'X' else 'X'

if __name__ == "__main__":
    main()