Minimaxアルゴリズム内のスレッディング

Question

私は3D Tic-Tac-Toeゲームを設計しており、Minimaxアルゴリズムがどれくらい深く進むことができるかの限界となる時間を見いだしています。深さ6まではほとんど時間的に重要ではありませんが（< 1秒）、深度が深ければ時間がかかります。

>Depth 7 = 6 seconds 
>Depth 8 = 49 seconds 
>Depth 9 = 314 seconds 

私は、より高い深度をチェックする時間がありませんでした。最大深度は22で、AIはMove 1からのすべての可能なゲーム状態を分析し、決してユーザーに勝つことはありません。

Minimax関数でスレッドを実装したいのですが、スレッディングに比較的新しいスレッドです。

//player is -1 for human, +1 for AI 
function minimax(board_state, depth, player) 
    if depth <= 0 or board == full //full board means no further states 
     return score * player 
    bestScore = -1000; 
    foreach possible move 
     if valid move 
      /* */ 
      make_move() 
      bestScore = max(bestScore, minimax(board_state, depth-1, -player) 
      undo_move() 
      /* */ 
    return bestScore 

私は/* */間のビットは、新たなスレッドです何かをしたいのですが、問題が発生する：私のミニマックス関数は以下のようであってもdepth = 1で、それは8つのスレッドです。 depth = 8については、スレッド数は16534863です。スレッドの制限は何ですか？それは私のCPUが持っている物理的なコアの数にリンクされていますか？

Answer 1

まず、8コアシステムでどれだけスピードアップできるのかを考えてみましょう。これは8倍です（問題がメモリに繋がっていない限り少し上手くいくことはできません）。 Amdahl's lawとGustafson's law

問題はa！Nの問題のように見えますが、時間がたつと爆発します。コードの変更を検討して、オプションの量を大幅に削減する必要があります。

あなたはすでにあなたのminmaxアルゴリズムでゲーム理論の方法を行っているようです。

ツリーの1つの深さで反対側のプレイヤーの勝利の動きを見つけたら、残りの可能な移動をテストする必要はなく、その部分木の勝者を返すことができます。

Answer 2

解決策はマルチスレッドではありません。 代わりにAlpha–beta pruningを調べてみてください。純粋なミニマックスは多くの冗長ノードを探索することになります。あなたが持っているので、この位置は勝利である

oxo 
oxx 
xox 

に対し：

また、私はあなたのコードでは、誰が勝っていないことを意味する、

return score * player 

フルボードの可能性が高いドローを意味で間違っていますfurhterを探索する代わりにスコアを返します。

xxx 
0 
0 

Answer 3

Tic Tac Toe、01の完璧な戦略があります。私はJavaScriptのゲームでそれを実装しており、それは簡単です。スレッドなし、アルファベータプルーニング、ミニマムなし、何もなし...

完璧なスタートガーは2つ前の動き（相手のフォークをブロックする）を見ていないので、それをライブで使うことができます。

メモ：ティックタックのつま先のボードは非常に対称的なので、使用する方法によって有効な移動回数を大幅に減らすことができます。あなたが完璧な戦略を見ているならば、移動回数はクラス（"センター"、 "反対側のコーナー"、 "エンプティコーナー"、 "エンプティサイド"など）で集計されます。