我正在尝试实现一种类似于 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 计算该特定骰子值的合法移动。
方法 2（通过印迹）
使用这种方法，我首先找到所有的印迹，然后对于每个印迹，我循环遍历每个可能的骰子值并查看是否发生命中。该功能经过优化，因此一旦骰子值记录了命中，我就不会再将它用于下一个印迹。它还经过优化，仅考虑印迹前面的移动。我的代码：
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;
}
方法transitions.HitBlot2 采用一个blotPosition 参数，确保只考虑那些在印迹前面的移动。
这两种实现都很慢，当我使用分析器时，我发现递归是原因，所以我尝试重构它们如下：
- 使用 for 循环而不是递归（丑陋的代码，但它更快）
- 要使用parallel.foreach，而不是一次检查1个骰子值，我会并行检查这些值。
这是我运行 50000 次功能计算的平均计时结果（请注意，每种方法的计时都是使用相同的数据完成的）：
- 使用递归的方法 1：每次计算 2.28 毫秒
- 使用递归的方法 2：每次计算 1.1 ms
- 使用 for 循环的方法 1：每次计算 1.02 毫秒
- 使用 for 循环的方法 2：每次计算 0.57 毫秒
- 使用 parallel.foreach 的方法 1：每次计算 0.75 毫秒 6 使用 parallel.foreach 的方法 2：每次计算 0.75 毫秒
我发现时间非常不稳定（可能取决于神经网络权重的随机初始化），但大约 0.7 毫秒似乎是可以实现的，如果你回想一下，这会导致 1,000,000 场比赛的 12 天训练。
我的问题是：有谁知道这是否合理？有没有我不知道的更快的算法可以减少训练？
最后一条信息：我正在一台相当新的机器上运行。英特尔 Cote (TM) i7-5500U CPU @2.40 GHz。
需要更多信息，请告诉我，我会提供。
谢谢， 奥菲尔