使用MinMax算法实现并玩四子棋游戏

Question

我正在尝试为四子棋（或连接4或连四）游戏实现MinMax算法。

我认为我已经理解了它的思路，应该建立一个可能的棋盘树到一定深度，评估它们并返回它们的分数，然后我们只需要取这些分数的最大值。

因此，aiChooseCol()通过调用MinMax()检查每个可能列的分数，并返回具有最高分数的列。

现在我不确定，这是调用MinMax()的正确方式吗？

检查temp = Math.Max(temp, 1000)是正确的吗？

我还没有制作启发式函数，但这应该至少识别出一个获胜的列并选择它，但目前它只是选择从左边开始的第一个空闲列...我无法弄清楚我做错了什么。

private int AiChooseCol()
{
    int best = -1000;
    int col=0;
    for (int i = 0; i < m_Board.Cols; i++)
    {
        if (m_Board.CheckIfColHasRoom(i))
        {
            m_Board.FillSignInBoardAccordingToCol(i, m_Sign);
            int t = MinMax(5, m_Board, board.GetOtherPlayerSign(m_Sign));
            if (t > best)
            {
                best = t;
                col = i;
            }
            m_Board.RemoveTopCoinFromCol(i);
        }

    }
    return col;
}


private int MinMax(int Depth, board Board, char PlayerSign)
{
    int temp=0;
    if (Depth <= 0)
    {
        // return from heurisitic function
        return temp;
    }
    char otherPlayerSign = board.GetOtherPlayerSign(PlayerSign);

    char checkBoard = Board.CheckBoardForWin();
    if (checkBoard == PlayerSign)
    {
        return 1000;
    }
    else if (checkBoard == otherPlayerSign)
    {
        return -1000;
    }
    else if (!Board.CheckIfBoardIsNotFull())
    {
        return 0;   // tie
    }


    if (PlayerSign == m_Sign)   // maximizing Player is myself
    {
        temp = -1000;
        for (int i = 0; i < Board.Cols; i++)
        {
            if (Board.FillSignInBoardAccordingToCol(i, PlayerSign)) // so we don't open another branch in a full column
            {
                var v = MinMax(Depth - 1, Board, otherPlayerSign);
                temp = Math.Max(temp, v);
                Board.RemoveTopCoinFromCol(i);
            }
        }
    }
    else
    {
        temp = 1000;
        for (int i = 0; i < Board.Cols; i++)
        {
            if (Board.FillSignInBoardAccordingToCol(i, PlayerSign)) // so we don't open another branch in a full column
            {
                var v = MinMax(Depth - 1, Board, otherPlayerSign);
                temp = Math.Min(temp, v);
                Board.RemoveTopCoinFromCol(i);
            }
        }
    }
    return temp;
}

一些注释：

FillSignInBoardAccordingToCol() 返回一个布尔值表示是否成功。

board 类型有一个包含实际棋盘和玩家标记的 char[,] 数组。

这段代码位于 AI 玩家类中。

- shinzou

---

在 AiChooseCol 中，您没有将列 i 传递给 MinMax，那么它如何知道您要求它评估哪一列？ - juharr

是的，我知道它可以进行重构。但修复AiChooseCol后仍无法正常工作。@juharr - shinzou

你应该在else分支中取Min值，而不是Max。而且由于这是唯一的区别，所以你应该将if-else放在这部分代码周围。 - juharr

请等待您的 Min 和 Max 调用将前一个 temp 与递归调用的返回值进行比较，而不是与最大和最小值进行比较。因此，您需要将其分配给变量 var v = MinMax(...);，然后执行 temp = Math.Max(temp, v);。并且 temp 应该根据它是否为最大化玩家来初始化为 1000 或 -1000。 - juharr

好的，我编辑了问题中的更改，但它仍然无法工作... @juharr - shinzou

Answer 1

于是我决定自己编写MinMax Connect 4。我使用深度来确定胜利或失败的价值，因此移动可以更接近获胜或阻止失败将优先考虑。如果有多个移动具有相同的启发式，则我会随机选择移动。最后，我将深度扩展到6，因为这是从开始找到可能的获胜路径所需的步骤数。

private static void Main(string[] args)
{
    var board = new Board(8,7);
    var random = new Random();

    while (true)
    {
        Console.WriteLine("Pick a column 1 -8");
        int move;
        if (!int.TryParse(Console.ReadLine(), out move) || move < 1 || move > 8)
        {
            Console.WriteLine("Must enter a number 1-8.");
            continue;
        }

        if (!board.DropCoin(1, move-1))
        {
            Console.WriteLine("That column is full, pick another one");
            continue;
        }

        if (board.Winner == 1)
        {
            Console.WriteLine(board);
            Console.WriteLine("You win!");
            break;
        }

        if (board.IsFull)
        {
            Console.WriteLine(board);
            Console.WriteLine("Tie!");
            break;
        }

        var moves = new List<Tuple<int, int>>();
        for (int i = 0; i < board.Columns; i++)
        {
            if (!board.DropCoin(2, i))
                continue;
            moves.Add(Tuple.Create(i, MinMax(6, board, false)));
            board.RemoveTopCoin(i);
        }

        int maxMoveScore = moves.Max(t => t.Item2);
        var bestMoves = moves.Where(t => t.Item2 == maxMoveScore).ToList();
        board.DropCoin(2, bestMoves[random.Next(0,bestMoves.Count)].Item1);
        Console.WriteLine(board);

        if (board.Winner == 2)
        {
            Console.WriteLine("You lost!");
            break;
        }

        if (board.IsFull)
        {
            Console.WriteLine("Tie!");
            break;
        }
    }

    Console.WriteLine("DONE");
    Console.ReadKey();
}

private static int MinMax(int depth, Board board, bool maximizingPlayer)
{
    if (depth <= 0)
        return 0;

    var winner = board.Winner;
    if (winner == 2)
        return depth;
    if (winner == 1)
        return -depth;
    if (board.IsFull)
        return 0;


    int bestValue = maximizingPlayer ? -1 : 1;
    for (int i = 0; i < board.Columns; i++)
    {
        if (!board.DropCoin(maximizingPlayer ? 2 : 1, i))
            continue;
        int v = MinMax(depth - 1, board, !maximizingPlayer);
        bestValue = maximizingPlayer ? Math.Max(bestValue, v) : Math.Min(bestValue, v);
        board.RemoveTopCoin(i);
    }

    return bestValue;
}

public class Board
{
    private readonly int?[,] _board;

    private int? _winner;

    private bool _changed;

    public Board(int cols, int rows)
    {
        Columns = cols;
        Rows = rows;
        _board = new int?[cols, rows];
    }

    public int Columns { get; }
    public int Rows { get; }

    public bool ColumnFree(int column)
    {
        return !_board[column, 0].HasValue;
    }

    public bool DropCoin(int playerId, int column)
    {
        int row = 0;
        while (row < Rows && !_board[column,row].HasValue)
        {
            row++;
        }

        if (row == 0)
            return false;
        _board[column, row - 1] = playerId;
        _changed = true;
        return true;
    }

    public bool RemoveTopCoin(int column)
    {
        int row = 0;
        while (row < Rows && !_board[column, row].HasValue)
        {
            row++;
        }

        if (row == Rows)
            return false;
        _board[column, row] = null;
        _changed = true;
        return true;
    }

    public int? Winner
    {
        get
        {
            if (!_changed)
                return _winner;

            _changed = false;
            for (int i = 0; i < Columns; i++)
            {
                for (int j = 0; j < Rows; j++)
                {
                    if (!_board[i, j].HasValue)
                        continue;

                    bool horizontal = i + 3 < Columns;
                    bool vertical = j + 3 < Rows;

                    if (!horizontal && !vertical)
                        continue;

                    bool forwardDiagonal = horizontal && vertical;
                    bool backwardDiagonal = vertical && i - 3 >= 0;

                    for (int k = 1; k < 4; k++)
                    {
                        horizontal = horizontal && _board[i, j] == _board[i + k, j];
                        vertical = vertical && _board[i, j] == _board[i, j + k];
                        forwardDiagonal = forwardDiagonal && _board[i, j] == _board[i + k, j + k];
                        backwardDiagonal = backwardDiagonal && _board[i, j] == _board[i - k, j + k];
                        if (!horizontal && !vertical && !forwardDiagonal && !backwardDiagonal)
                            break;
                    }

                    if (horizontal || vertical || forwardDiagonal || backwardDiagonal)
                    {
                        _winner = _board[i, j];
                        return _winner;
                    }
                }
            }

            _winner = null;
            return _winner;
        }
    }

    public bool IsFull
    {
        get
        {
            for (int i = 0; i < Columns; i++)
            {
                if (!_board[i, 0].HasValue)
                    return false;
            }

            return true;
        }
    }

    public override string ToString()
    {
        var builder = new StringBuilder();
        for (int j = 0; j < Rows; j++)
        {
            builder.Append('|');
            for (int i = 0; i < Columns; i++)
            {
                builder.Append(_board[i, j].HasValue ? _board[i,j].Value.ToString() : " ").Append('|');
            }
            builder.AppendLine();
        }

        return builder.ToString();
    }
}

- juharr

---

你的算法在深度为6时真的很快，而我的即使不调用启发式函数，在这个深度上也非常慢。在早期游戏中，深度5需要大约1秒钟，但是你的算法明显更快，为什么呢？ - shinzou

你将isFull转换为属性，非常聪明。winner方法不会多次检查许多坐标吗？（即使在相同的方向上） - shinzou

“Winner” 循环遍历每个位置，将其视为四个连接的起点：向下、向右、向右下对角线或向左下对角线。然后它可能会查看这些方向上的最多12个位置，因此从某种意义上说，它确实会重复查看某些位置，但这是因为一个位置可以成为最多16个不同的可能连接4场景的一部分（在至少为7x7的棋盘上）。 - juharr

它帮助我完成了我的作业，非常感谢。 - t4taurus