here で説明されているように、td-gammon に似たバックギャモンのアルゴリズムを実装しようとしています。
論文で説明されているように、td-gammon の初期バージョンは、優れたプレー エージェントを作成する特徴空間で生のボード エンコーディングのみを使用していましたが、世界クラスのエージェントを取得するには、優れたプレーに関連するいくつかの事前計算された特徴を追加する必要があります。遊ぶ。最も重要な機能の 1 つは、しみの露出です。
ブロット露出は次のように定義されます。
特定のブロットについて、対戦相手がブロットをヒットできるようにする 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 とすると、1,000,000 ゲームをシミュレートするのに約 12 日かかります。
それが妥当なタイミングかどうかはよくわかりませんが、かなり速いアプローチが必要だと感じています。
だからここに私が試したことがある：
アプローチ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] になります)。関数は、ヒットがあるかどうかを再帰的にチェックします。関数 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 ミリ秒
- for ループを使用したアプローチ 1: 計算あたり 1.02 ミリ秒
- for ループを使用したアプローチ 2: 計算あたり 0.57 ミリ秒
- parallel.foreach を使用したアプローチ 1: 計算あたり 0.75 ミリ秒 6 parallel.foreach を使用したアプローチ 2: 計算あたり 0.75 ミリ秒
タイミングが非常に不安定であることがわかりました (ニューラル ネットワークの重みのランダムな初期化に依存する可能性があります) が、約 0.7 ミリ秒が達成可能であるように思われます。
私の質問は次のとおりです。これが合理的かどうか知っている人はいますか? トレーニングを減らすことができる、私が認識していないより高速なアルゴリズムはありますか?
最後の情報: 私はかなり新しいマシンで実行しています。Intel Cote (TM) i7-5500U CPU @2.40 GHz。
さらに情報が必要な場合はお知らせください。提供いたします。
ありがとう、オフィル