井字棋AI策略第4步：阻止对手Fork功能实现故障排查

维基百科井字棋策略引用 #

引用自维基百科（井字棋#策略）
玩家若每回合按以下列表优先选择可行走法，即可完美下井字棋（获胜或至少平局），该策略用于Newell和Simon1972年的井字棋程序。[6]

1. 获胜：若己方已有两子连线，补下第三子完成三子连线。
2. 阻挡：若对手已有两子连线，补下第三子阻止其获胜。
3. Fork：创造能从两种方式获胜的机会。
4. 阻止对手的Fork：
   • 选项1：创造己方两子连线迫使对手防御，前提是此举不会让对手形成Fork或获胜。例如，若X占据一角，O占据中心，X又占据对角，则O不能下在角落，否则会给X创造Fork机会使其获胜。
   • 选项2：若存在对手可形成Fork的局面，直接阻挡该Fork点。
5. 中心：下在棋盘中心。
6. 对角：若对手在角落，下在其对角位置。
7. 空角落：下在空的角落位置。
8. 空边：下在空的边位。

问题描述 #

我在实现该算法的第4步（阻止对手Fork）时遇到问题，对应代码中的select_blocking_fork_move函数。

AI自我对局示例 #

. . . . . . .
   . . . . . . .
   . . . . . . .
   . . . X . . .
   . . . . . . .
   . . . . . . .
   . . . . . . .
   

   . . . . . . .
   . . . . . . .
   . . . . . . .
   . . . X . . O
   . . . . . . .
   . . . . . . .
   . . . . . . .
   

   . . . . . . .
   . . . . . . .
   . . . . . . .
   . . . X . . O
   . . . . . . .
   . . . . . . .
   . . . X . . .
   
   . . . . . . .
   . . . . . . .
   . . . . . . .
   . . . X . . O
   . . . . . . .
   . . . . . . .
   . . . X . . O

// 此处O不应下在右下角，而应下在中心X的右侧以阻挡X的Fork。

   . . . . . . .
   . . . . . . .
   . . . . . . .
   . . . X X . O
   . . . . . . .
   . . . . . . .
   . . . X . . O

   . . . . . . .
   . . . . . . .
   . . . . . . .
   . . O X X . O
   . . . . . . .
   . . . . . . .
   . . . X . . O

   . . . . . . .
   . . . . . . .
   . . . . . . .
   . . O X X X O
   . . . . . . .
   . . . . . . .
   . . . X . . O

X获胜！

完整代码 #

#include "the_player.h"
#include <iostream>
#include <algorithm>
#include <random>

THE_PLAYER::THE_PLAYER(const std::string& name) : _name(name), _mark(Mark::None), _opponent_mark(Mark::None) {}

std::string THE_PLAYER::get_name() const {
    return _name;
}

Mark THE_PLAYER::get_mark() const {
    return _mark;
}

void THE_PLAYER::assign_mark(Mark player_mark) {
    _mark = player_mark;
    _opponent_mark = (_mark == Mark::Cross) ? Mark::Zero : Mark::Cross;
}

void THE_PLAYER::notify(const GameView& view, const Event& event) {
    // Implement if needed
}

bool THE_PLAYER::is_valid_move(const GameView& game, const Point& move) const {
    const auto& field = game.get_state().field;
    return field->get_value(move) == Mark::None;
}

bool THE_PLAYER::is_winning_move(const GameView& game, const Point& move, Mark mark) const {
    const auto& field = game.get_state().field;
    const auto& settings = game.get_settings();
    int win_length = settings.win_length;

    const std::vector<std::pair<int, int>> directions = { {1, 0}, {0, 1}, {1, 1}, {1, -1} };
    for (const auto& dir : directions) {
        int count = 1;
        for (int i = 1; i < win_length; ++i) {
            Point p = { move.x + i * dir.first, move.y + i * dir.second };
            if (!settings.field_size.is_within(p) || field->get_value(p) != mark) break;
            ++count;
        }
        for (int i = 1; i < win_length; ++i) {
            Point p = { move.x - i * dir.first, move.y - i * dir.second };
            if (!settings.field_size.is_within(p) || field->get_value(p) != mark) break;
            ++count;
        }
        if (count >= win_length) return true;
    }
    return false;
}

std::vector<Point> THE_PLAYER::get_empty_cells(const GameView& game) const {
    std::vector<Point> empty_cells;
    const auto& field = game.get_state().field;
    const auto& boundary = field->get_current_boundary();

    for (int y = boundary.min.y; y <= boundary.max.y; ++y) {
        for (int x = boundary.min.x; x <= boundary.max.x; ++x) {
            Point p = { x, y };
            if (field->get_value(p) == Mark::None) {
                empty_cells.push_back(p);
            }
        }
    }
    return empty_cells;
}

Point THE_PLAYER::get_best_move(const GameView& game) const {
    const auto& field = game.get_state().field;
    auto empty_cells = get_empty_cells(game);

    // Win
    for (const auto& move : empty_cells) {
        if (is_winning_move(game, move, _mark)) {
            return move;
        }
    }

    // Block
    for (const auto& move : empty_cells) {
        if (is_winning_move(game, move, _opponent_mark)) {
            return move;
        }
    }

    // Fork
    for (const auto& move : empty_cells) {
        if (creates_fork(game, move, _mark)) {
            return move;
        }
    }

    // Block opponent's fork using select_blocking_fork_move
    Point blocking_fork_move = select_blocking_fork_move(game);
    if (blocking_fork_move.x != -1 && blocking_fork_move.y != -1) {
        return blocking_fork_move;
    }

    // Center
    Point center = { (field->get_current_boundary().min.x + field->get_current_boundary().max.x) / 2,
                     (field->get_current_boundary().min.y + field->get_current_boundary().max.y) / 2 };
    if (is_valid_move(game, center)) {
        return center;
    }

    // Opposite Corner
    for (const auto& move : empty_cells) {
        if (is_opposite_corner(game, move)) {
            return move;
        }
    }

    // Empty Corner or Empty Side
    for (const auto& move : empty_cells) {
        if (is_empty_corner(game, move) || is_empty_side(game, move)) {
            return move;
        }
    }

    // Random move
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, empty_cells.size() - 1);
    return empty_cells[dis(gen)];
}

bool THE_PLAYER::creates_fork(const GameView& game, const Point& move, Mark mark) const {
    const auto& field = game.get_state().field;
    const auto& settings = game.get_settings();
    int win_length = settings.win_length;
    int fork_count = 0;

    // Temporarily make the move
    field->set_value(move, mark);

    // Check for potential wins in all directions
    const std::vector<std::pair<int, int>> directions = { {1, 0}, {0, 1}, {1, 1}, {1, -1} };

    for (const auto& dir : directions) {
        int potential_wins = 0;

        for (int i = -win_length + 1; i < win_length; ++i) {
            int count = 0;
            int empty_count = 0;

            for (int j = 0; j < win_length; ++j) {
                Point p = { move.x + (i + j) * dir.first, move.y + (i + j) * dir.second };

                if (!settings.field_size.is_within(p)) break;

                Mark cell_mark = field->get_value(p);

                if (cell_mark == mark) {
                    count++;
                }
                else if (cell_mark == Mark::None) {
                    empty_count++;
                }
                else {
                    break; // Opponent's mark found, not a potential win
                }
            }

            if (count == win_length - 1 && empty_count == 1) {
                potential_wins++;
            }

            if (potential_wins > 1) {
                fork_count++;
                break;
            }
        }

        if (fork_count >= 2) {
            // Revert the move and return true if a fork is found
            field->set_value(move, Mark::None);
            return true;
        }
    }

    // Revert the move
    field->set_value(move, Mark::None);

    return false;
}

Point THE_PLAYER::select_blocking_fork_move(const GameView& game) const {
    const auto& field = game.get_state().field;
    auto empty_cells = get_empty_cells(game);
    std::vector<Point> possible_moves;

    // Find all possible opponent forks
    for (const auto& move : empty_cells) {
        if (creates_fork(game, move, _opponent_mark)) {
            possible_moves.push_back(move);
        }
    }

    if (possible_moves.empty()) {
        return { -1, -1 }; // No forks to block
    }

    // Evaluate each possible move to block the forks
    for (const auto& move : possible_moves) {
        // Simulate the blocking move directly on the field
        field->set_value(move, _mark);

        // Check if the opponent has a winning move after this
        Point opponent_move = get_best_move(game);
        if (is_winning_move(game, opponent_move, _opponent_mark)) {
            field->set_value(opponent_move, _opponent_mark);

            // If the opponent's move doesn't create a fork, return this move
            if (!creates_fork(game, opponent_move, _opponent_mark)) {
                field->set_value(move, Mark::None); // Revert the move
                field->set_value(opponent_move, Mark::None); // Revert opponent's move
                return move;
            }

            // Revert the opponent's simulated move
            field->set_value(opponent_move, Mark::None);
        }
        else {
            // If the opponent doesn't have a winning move, return this move
            field->set_value(move, Mark::None); // Revert the move
            return move;
        }

        // Revert the simulated move
        field->set_value(move, Mark::None);
    }

    // If no suitable blocking move found, return the first valid move
    return possible_moves.front();
}



bool THE_PLAYER::is_opposite_corner(const GameView& game, const Point& move) const {
    const auto& settings = game.get_settings();
    int max_x = settings.field_size.max.x;
    int max_y = settings.field_size.max.y;

    return (move.x == 0 && move.y == 0) || (move.x == max_x && move.y == max_y) ||
        (move.x == 0 && move.y == max_y) || (move.x == max_x && move.y == 0);
}

bool THE_PLAYER::is_empty_corner(const GameView& game, const Point& move) const {
    const auto& settings = game.get_settings();
    int max_x = settings.field_size.max.x;
    int max_y = settings.field_size.max.y;

    return ((move.x == 0 && move.y == 0) || (move.x == 0 && move.y == max_y) ||
        (move.x == max_x && move.y == 0) || (move.x == max_x && move.y == max_y));
}

bool THE_PLAYER::is_empty_side(const GameView& game, const Point& move) const {
    const auto& settings = game.get_settings();
    int max_x = settings.field_size.max.x;
    int max_y = settings.field_size.max.y;

    return ((move.x == 1 && move.y == 0) || (move.x == 0 && move.y == 1) ||
        (move.x == 1 && move.y == max_y) || (move.x == max_x && move.y == 1));
}

Point THE_PLAYER::play(const GameView& game) {
    return get_best_move(game);
}

请求协助 #

恳请协助排查select_blocking_fork_move函数的逻辑问题，使AI能正确执行阻止对手Fork的策略。

内容的提问来源于stack exchange，提问作者Med Salem