如何有效地计算双陆棋中的斑点曝光

我正在尝试实现一个类似于这里描述的td-gammon的双陆棋算法。

如文中所述，td-gammon的初始版本仅在特征空间中使用原始棋盘编码，从而创建了一个优秀的游戏代理，但要获得世界级的代理，您需要添加一些与优秀游戏相关的预计算特征。最重要的特征之一是印迹曝光。

印迹暴露在这里定义为:

对于给定的污点，在36次投掷中允许对手击中污点的次数。总污点暴露是36个滚出的数量，这将允许对手击中任何污点。印迹暴露取决于:(a)印迹前所有敌方人员的位置;(b)污渍和敌人之间的阻挡点的数量和位置;(c)杠上的敌人的数量，以及允许他们重新进入板的滚动，因为杠上的人必须在污渍被击中之前重新进入。

我已经尝试了各种方法来有效地计算这个特征，但我的计算仍然太慢，我不确定如何加快它。

请记住，td-gammon方法评估给定骰子滚动的每个可能的棋盘位置，所以每个玩家骰子滚动的每个回合，你都需要为每个可能的棋盘位置计算这个功能。

一些粗略的数字:假设每个回合大约有30个棋盘位置，平均游戏持续50个回合，我们得到运行1,000,000个游戏模拟需要:(x * 30 * 50 * 1,000,000)/(1000 * 60 * 60 * 24)天，其中x是计算特征的毫秒数。假设x = 0.7，我们可以在12天内模拟1,000,000场游戏。

我不知道这个时机是否合理，但我觉得必须有一个明显更快的方法。

我试过了:

方法1(通过掷骰子)

对于21个可能掷出的骰子中的每一个，递归检查是否命中。下面是这个过程的主要工作:

private bool HitBlot(int[] dieValues, Checker.Color checkerColor, ref int depth)
    {
        Moves legalMovesOfDie = new Moves();
        if (depth < dieValues.Length)
        {
            legalMovesOfDie = LegalMovesOfDie(dieValues[depth], checkerColor);
        }
        if (depth == dieValues.Length || legalMovesOfDie.Count == 0)
        {
            return false;
        }
        bool hitBlot = false;
        foreach (Move m in legalMovesOfDie.List)
        {
            if (m.HitChecker == true)
            {
                return true;
            }
            board.ApplyMove(m);
            depth++;
            hitBlot = HitBlot(dieValues, checkerColor, ref depth);
            board.UnapplyMove(m);
            depth--;
            if (hitBlot == true)
            {
                break;
            }
        }
        return hitBlot;
    }

这个函数的作用是将骰子值数组作为输入(例如，如果玩家掷1,1，数组将是[1,1,1,1])。然后，该函数递归地检查是否有命中，如果有命中，则返回true。函数LegalMovesOfDie计算特定骰子值的合法移动。

方法二(印迹法)

使用这种方法，我首先找到所有的斑点，然后对于每个斑点，我循环遍历每个可能的骰子值，看看是否发生命中。该函数经过优化，以便一旦骰子值注册命中，我就不会再次使用它进行下一个污点。它也被优化为只考虑在斑点前面的动作。我的代码:

public int BlotExposure2(Checker.Color checkerColor)
    {
        if (DegreeOfContact() == 0 || CountBlots(checkerColor) == 0)
        {
            return 0;
        }
        List<Dice> unusedDice = Dice.GetAllDice();
        List<int> blotPositions = BlotPositions(checkerColor);
        int count = 0;
        for(int i =0;i<blotPositions.Count;i++)
        {
            int blotPosition = blotPositions[i];
            for (int j =unusedDice.Count-1; j>= 0;j--) 
            {
                Dice dice = unusedDice[j];
                Transitions transitions = new Transitions(this, dice);
                bool hitBlot = transitions.HitBlot2(checkerColor, blotPosition);
                if(hitBlot==true)
                {
                    unusedDice.Remove(dice);
                    if (dice.ValuesEqual())
                    {
                        count = count + 1;
                    }
                    else
                    {
                        count = count + 2;
                    }
                } 
            }
        }

        return count;
    }

方法转换。HitBlot2接受一个blotPosition参数，该参数确保只考虑位于blotPosition前面的移动。

这两个实现都非常慢，当我使用分析器时，我发现递归是原因，所以我试着重构它们如下:

使用for循环代替递归(代码很丑，但速度快得多)
使用并行。foreach这样，而不是一次检查一个骰子值，我检查这些并行。

下面是我运行50000次特征计算的平均计时结果(注意每种方法的计时都是对相同的数据进行的):

使用递归的方法1:每次计算2.28 ms
使用递归的方法2:每次计算1.1 ms
方法1使用for循环:1.02 ms每次计算
方法2使用for循环:0.57 ms每次计算
方法1使用并行。Foreach:每次计算0.75 ms6使用并行方法2。foreach: 0.75 ms每次计算

我发现时间相当不稳定(可能取决于神经网络权重的随机初始化)，但大约0.7毫秒似乎是可以实现的，如果你记得的话，需要12天的时间来训练1,000,000个游戏。

我的问题是:有人知道这是合理的吗?有没有我不知道的更快的算法可以减少训练?

最后一点信息:我在一台相当新的机器上运行。Intel Cote (TM) i7-5500U CPU @2.40 GHz

如果需要更多的信息，请告诉我，我将提供。

谢谢,方法

是的，计算这些特性会使代码变得非常复杂。看看GNU Backgammon代码。找到eval.c并查看1008到1267的行。是的，它有260行代码。该代码计算至少击中一个检查器的掷骰次数，以及至少击中两个检查器的掷骰次数。如您所见，代码很复杂。

如果你找到一个更好的方法来计算这个，请发布你的结果。为了改进，我认为你必须看看董事会的代表性。你能不能用另一种方式来表示棋盘，使计算更快?

相关内容

最新更新

热门标签：