65.9K
CodeProject 正在变化。 阅读更多。
Home

双陆棋人工智能

KristianEkman
starIconstarIconstarIconstarIconstarIcon

5.00/5 (20投票s)

2021年4月22日

CPOL

7分钟阅读

viewsIcon

48246

downloadIcon

846

如何构建一个玩双陆棋的人工智能

目录

引言

本文演示了如何构建一个会玩西洋双陆棋的AI。
您也可以在这里在线与它对战。

这是我发布的第二篇关于在线西洋双陆棋的文章。
如果您想了解更多关于在线应用程序的信息，请阅读第一篇文章。
在这篇文章中，我将重点放在AI算法上。

这个第一版中的AI相当简单。总而言之，从给定的棋盘状态和给定的掷骰结果，生成所有可能的走法决策，并为每个选择计算一个分数。
最高分决定了AI的最佳走法。

但是，也许我应该更详细地写一点，否则这篇文章会很短。

数据模型

数据模型的选择非常重要，它是您构建其他一切的基础。
由于这是我的第一个西洋双陆棋应用程序，我觉得我必须使用C#和一个面向对象的模型。C#是我最熟悉的编程语言。

几年前，我用C#和C编写了国际象棋引擎，当涉及到性能和计算速度时，选择C当然会得到更强大的机器。它的运行速度快了好几个数量级。

以下是类和最重要的属性

class Game
     Player Black
     Player White
     List<Point> Points
     List<Move> ValidMoves
        
class Point
     List<Check> Checkers
        
class Checker
     PlayerColor Color
        
enum PlayerColor 
     Black
     White

如果您玩过西洋双陆棋，我想您知道有两个玩家。我称他们为黑方和白方。每个玩家有15个棋子。它们最初放置在棋盘点上。棋盘上有24个点。

每个玩家还有一个家，即点25，以及点数为0的酒吧。这些点对于白方来说是倒序编号的。因此，白方的点1就是黑方的点24，依此类推。这很有道理，因为玩家们向相反的方向移动他们的棋子。

不过我在这个设计中犯了一个错误。一个玩家的家点（25）也将是另一个玩家的酒吧（0）。最好不要将家点包含在点数组中，但现在要改变它需要很大的努力。如果我出于性能原因而在C中实现该程序，这是我学到并会改变的一件事。

走法生成

一次移动只是将一个棋子放置在一个新点上。
由于一次掷骰会生成每回合的几次移动，因此需要评估的不仅仅是一次移动，而是一系列移动。
因此，走法生成函数会生成所有可能的走法序列列表。

public static List<Move[]> GenerateMovesSequence(Game game)
{
    var sequences = new List<Move[]>();
    var moves = new Move[game.Roll.Count];
    sequences.Add(moves);
    GenerateMovesSequence(sequences, moves, 0, game);
... and so on
    return sequences;
}

private static void GenerateMovesSequence(List<Move[]> sequences, 
        Move[] moves, int diceIndex, Game game)
{
    var current = game.CurrentPlayer;
    var bar = game.Bars[(int)current];
    var barHasCheckers = bar.Checkers.Any(c => c.Color == current);
    var dice = game.Roll[diceIndex];
    var points = barHasCheckers ? new[] { bar } :
        game.Points.Where(p => p.Checkers.Any(c => c.Color == current))
        .ToArray();

    // There seems to be a big advantage to evaluate points from lowest number.
    // If not reversing here, black will win 60 to 40 with same config.
    if (game.CurrentPlayer == Player.Color.White)
        Array.Reverse(points);

    foreach (var fromPoint in points)
    {
        var fromPointNo = fromPoint.GetNumber(game.CurrentPlayer);
        if (fromPointNo == 25)
            continue;
        var toPoint = game.Points.SingleOrDefault
        (p => p.GetNumber(game.CurrentPlayer) == dice.Value + fromPointNo);
        if (toPoint != null && toPoint.IsOpen(game.CurrentPlayer)
            && !toPoint.IsHome(game.CurrentPlayer)) // no creation of bearing off moves here.
                                                    // See next block.
        {
            var move = new Move 
            { Color = game.CurrentPlayer, From = fromPoint, To = toPoint };
            //copy and make a new list for first dice
            if (moves[diceIndex] == null)
                moves[diceIndex] = move;
            else // a move is already generated for this dice in this sequence. 
                 // branch off a new.
            {
                var newMoves = new Move[game.Roll.Count];
                Array.Copy(moves, newMoves, diceIndex);
                newMoves[diceIndex] = move;
                // For last checker identical sequences are omitted.
                if (diceIndex < game.Roll.Count - 1 || 
                    !sequences.ContainsEntryWithAll(newMoves))
                {
                    moves = newMoves;
                    sequences.Add(moves);
                }
            }
            if (diceIndex < game.Roll.Count - 1) // Do the created move 
                                                 // and recurse to next dice
            {
                var hit = game.MakeMove(move);
                GenerateMovesSequence(sequences, moves, diceIndex + 1, game);
                game.UndoMove(move, hit);
            }
        }
    }
}

每次掷两个骰子都会生成两次或四次移动。（当骰子显示相同的值时，您可以使用它们两次。）
玩家的棋子可以处于“出局”模式，即当所有棋子都到达点19或更远，并且您被允许将它们移动到家点时。

在这种状态下，走法生成有特殊规则。

if (game.IsBearingOff(game.CurrentPlayer))
{
    // The furthest away checker can be moved beyond home.
    var minPoint = game.Points.Where(p => p.Checkers.Any
                   (c => c.Color == game.CurrentPlayer)).OrderBy
                   (p => p.GetNumber(game.CurrentPlayer)).
                   First().GetNumber(game.CurrentPlayer);
    var toPointNo = fromPointNo == minPoint ? Math.Min(25, fromPointNo + dice.Value) : 
                    fromPointNo + dice.Value;
    toPoint = game.Points.SingleOrDefault(p => p.GetNumber(game.CurrentPlayer) == toPointNo);
    if (toPoint != null && toPoint.IsOpen(game.CurrentPlayer))
    {
        var move = new Move { Color = game.CurrentPlayer, From = fromPoint, To = toPoint };
        if (moves[diceIndex] == null)
            moves[diceIndex] = move;
        else
        {
            var newMoves = new Move[game.Roll.Count];
            Array.Copy(moves, newMoves, diceIndex);
            newMoves[diceIndex] = move;
            // For last checker identical sequences are omitted.
            if (diceIndex < game.Roll.Count - 1 || !sequences.ContainsEntryWithAll(newMoves))
            {
                moves = newMoves;
                sequences.Add(moves);
            }
        }
        if (diceIndex < game.Roll.Count - 1)
        {
            var hit = game.MakeMove(move);
            GenerateMovesSequence(sequences, moves, diceIndex + 1, game);
            game.UndoMove(move, hit);
        }
    }
}

在某些棋盘位置，走一步棋会阻止另一个骰子移动，但在西洋双陆棋中，如果可能，所有骰子都必须使用。在走法生成后，走法较少的序列将被忽略。

if (sequences.Any(moves => moves.Any(m => m != null)))
                  sequences = sequences.Where
                 (moves => moves.All(m => m != null)).Select(s => s).ToList();

评估版

Points

显然，当对手剩余很多点，而AI剩余点数较少时，走法序列得分更高。顺便说一下，剩余点数在西洋双陆棋术语中称为“点子”。

private static double EvaluatePoints(Player.Color myColor, Game game)
{
    if (myColor == Player.Color.White)
        return game.BlackPlayer.PointsLeft - game.WhitePlayer.PointsLeft;
    else
        return game.WhitePlayer.PointsLeft - game.BlackPlayer.PointsLeft;
}

连接的棋墩（cb）

当一个点上有两个或更多棋子时，它就被堵住了，对手无法移动到那里。最好尝试在相邻位置创建棋墩，以完全阻止对手移动他们的棋子。连续棋墩的数量乘以一个常数（cb）会增加得分。

散子因子（bf）和已通过散子因子（bfp）

当您在一个点上留下一个棋子（一个散子）时，它可能会被对手击中并被移到酒吧，从头开始。留下一个散子会降低分数，降低的幅度是乘以一个因子（bf）再乘以散子点数。

但是，如果所有对手的棋子都已通过该散子，则在那里留下散子可能没那么糟糕。因此，会使用另一个较小的因子（bfp）。

散子阈值（bt）

很多时候，除了留下散子别无选择。最好留下点数较低的散子，在低点留下散子可能不是一个劣势。因为对手很可能不得不留下点数较高的散子来击中它。低于此阈值（bt）的散子不会对得分产生负面影响。

跑或挡（rb）

当您在点数上落后时，最好在棋盘早期留下一些棋子，而不是让所有棋子都超过对手。（当您遥遥领先时，您会想尽快跑回家）。这样，如果对手留下散子，您仍然有机会击中她。如果您所有的棋子都超过了对手，您的分数将受到点数差异乘以一个因子（rb）的影响。

var allPassed = true;
for (int i = 1; i < 25; i++)
{
    var point = game.Points[i];
    // Found that it's important to reverse looping for white. 
    // These conditions affect score for some configurations greatly.
    // But I haven't figured out why.
    if (myColor == Player.Color.White)
        point = game.Points[25 - i];
    // If all opponents checkers have passed this block or blot, it is not interesting.
    if (point.GetNumber(myColor) > opponentMax)
        break;
    allPassed = false;
    if (point.MyBlock(myColor))
    {
        if (inBlock)
            counter++;
        else
            counter = 1;
        inBlock = true;
    }
    else
    {
        if (inBlock)
        {
            score += Math.Pow(counter * cbp, cb);
            counter = 0;
        }
        inBlock = false;
        if (point.Blot(myColor) && point.GetNumber(myColor) > bt)
           score -= point.GetNumber(myColor) / ( allPassed ? bfp : bf);
    }
}

if (inBlock)
    score += Math.Pow(counter, 2);

if (allPassed)
    score += EvaluatePoints(myColor, game) * rb;

残局

当一个玩家的最后一个棋子通过另一个玩家的最后一个棋子时，评估变得简单得多。
AI首先尝试将所有棋子移入家中。然后将棋子从棋盘上移走。
不给予堵塞或散子分数。

培训

以上提到的所有这些常数都是引擎的配置。
它们的值应该是什么并不明显，所以优化它们是训练师的工作。
训练器让两个AI引擎互相玩3000次。如果被优化的AI赢得超过51%的比赛，其配置更改将被保存。然后训练重新开始。
因此，经过几个小时和大约一百万局游戏后，找到了最佳配置，AI就完成了。

概率分数

概率分数计算当前玩家掷出所有可能组合的平均分数。因此，AI不是选择评估最高的走法序列，而是走一步棋并计算对手的概率分数，选择对手平均分数最低的走法。这类似于深度为1的Minimax算法。

由于概率分数层增加了大量的计算时间，所以无法在启用此功能的情况下训练AI，但我认为在未来的C语言实现中这将成为可能。

但是，在比较启用和未启用概率分数的两个引擎时，它们的实力相当。我认为原因在于训练是在未启用概率分数的情况下进行的。因此，出于性能原因，它被禁用。

private double ProbabilityScore(Player.Color myColor, Game game)
{
    var allDiceRoll = AllRolls();
    var scores = new List<double>();
    var oponent = myColor == Player.Color.Black ? Player.Color.White : Player.Color.Black;
    foreach (var roll in allDiceRoll)
    {
        game.FakeRoll(roll.dice1, roll.dice2);
        var bestScore = double.MinValue;
        var seqs = GenerateMovesSequence(game);
        foreach (var s in seqs)
        {
            var hits = DoSequence(s, game);
            var score = EvaluatePoints(myColor, game) + EvaluateCheckers(myColor, game);
            score -= EvaluateCheckers(oponent, game);
            if (score > bestScore)
                bestScore = score;
            UndoSequence(s, hits, game);
        }
        int m = roll.dice1 == roll.dice2 ? 1 : 2; // dice roll with not same value 
                            // on dices are twice as probable. 2 / 36, vs 1 / 36
        if (seqs.Any())
            scores.Add(bestScore * m);
    }
    if (!scores.Any())
        return -100000; // If player can't move, she's blocked. That's bad.
    return scores.Average();
}

改变西洋双陆棋规则

应该说，运气在西洋双陆棋中是一个巨大的因素。未经训练的AI，其配置因子设置为零，仍能击败训练有素的AI，胜率为19.3%。
很多次我在玩在线西洋双陆棋时，落后了，我觉得如果我只掷出双五或双六，我仍然有机会赶上。所以我决定研究一下，如果您禁用“如果您掷出双倍，则移动四次”的规则会发生什么。结果是，使用这些规则，未经训练的AI对战训练有素的AI，胜率只有7%。我的结论是，如果您按照上述方式改变规则，结果将更多地取决于技巧。而且这也许会是一个更有趣的游戏。请在评论中告诉我您的想法。

链接

历史

  • 2021年4月22日：版本1.0
  • 2021年5月5日：版本1.1
    • 新增了上周游戏排行榜
  • 6月21日：版本3.1
    • 改进了带有已通过散子因子的AI
  • 6月26日：版本3.1.1
    • 使用姓名和密码的登录功能
  • 2022年4月25日。版本3.6
    • 改进了残局
    • 修复了走法生成错误
© . All rights reserved.