c++ - 为什么我的井字游戏 minimax 实现这么慢？

问题描述

我非常简单的井字游戏极小极大算法以每秒大约 500 万个节点的速度运行。尽管这足以在 0.1 秒内找到井字游戏，但比其他程序要少得多。例如，该视频在 10:00 显示，计算国际象棋走法（要复杂得多）的速度约为每秒 2000 万个节点。该网站显示，Stockfish 可以在普通 PC 上以每秒 500 万个节点的速度运行完整的国际象棋引擎。

代码：

#include <iostream>
#include <chrono>

int board[3][3];
int nodes = 0;

bool isFull()
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (board[i][j] == 0)
            {
                return false;
            }
        }
    }

    return true;
}

bool equals3(int a, int b, int c)
{
    return a == b && b == c && a > 0;
}

int checkWin()
{
    for (int row = 0; row < 3; row++)
    {
        if (equals3(board[row][0], board[row][1], board[row][2]))
        {
            return board[row][0];
        }

        if (equals3(board[0][row], board[1][row], board[2][row]))
        {
            return board[0][row];
        }
    }

    if (equals3(board[0][0], board[1][1], board[2][2]))
    {
        return board[0][0];
    }

    if (equals3(board[0][2], board[1][1], board[2][0]))
    {
        return board[0][2];
    }

    return 0;
}

int negaMax(int turn)
{
    nodes++;

    if (isFull())
    {
        return 0;
    }

    int win = checkWin();
    if (win != 0)
    {
        return (win == turn) ? 1 : -1;
    }

    int bestScore = -1;

    for (int x = 0; x < 3; x++)
    {
        for (int y = 0; y < 3; y++)
        {
            if (board[x][y] == 0)
            {
                board[x][y] = turn;
                int score = -negaMax(3 - turn);
                board[x][y] = 0;

                if (score > bestScore)
                {
                    bestScore = score;
                }
            }
        }
    }

    return bestScore;
}

int main()
{
    auto start = std::chrono::system_clock::now();

    negaMax(1);

    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> timePassed = end - start;
    
    std::cout << "Nodes searched: " << nodes << "\n";
    std::cout << "Time passed: " << timePassed.count() << "\n";
    std::cout << "NPS: " << nodes / timePassed.count() << "\n";
}

我不确定如何进一步改进这个程序，并且在我的国际象棋移动生成中显示出速度的不足。

标签： c++tic-tac-toeminimax

c++ - 为什么我的井字游戏 minimax 实现这么慢？

问题描述

解决方案

推荐阅读