5

私の AI クラスでは、アルファ ベータ プルーニングを使用して、量子三目並べゲームを作成する必要があります。

私はボードの状態を表現する最良の方法について考えています - 私の最初の直感は、一種の近傍行列、つまり 9x9 行列を使用することです.onM[i,j]は移動を表す整数です (tic-tac -toe) 四角iでjマークされています (そのような接続がない場合M[i,j]はゼロです)。M[i,i]正方形iが折りたたまれている場合は 0 ではありません。次に、そのような行列のゲーム ツリーを作成し、従来のミニマックスとアルファ ベータ プルーニングを使用します。

ただし、このアプローチは非常にコストがかかるようです。比較的大きな分岐係数に加えて、すべてのノードの基本操作が必要です。サイクルをチェックし、9x9 マトリックスのすべての同等の状態を見つけます。

よりスマートな解決策が必要だと感じています。おそらく、量子ゲームを古典的な三目並べゲームのセットと見なし、一種の一般化されたミニマックス検索を使用するようなものかもしれません。したがって、すべてが(小さい) 古典的な三目並べの問題のセット? それが正確にどのように機能するかわかりません。

誰かがこの（または同様の）問題の経験があり、正しい方向に私を向けることができますか?

4

2 に答える 2

0

問題がTic-Tac-Toeだけの場合は、このプログラムのようにボードを表現できますhttp://pastie.org/1715115

これは、3値ベースの数値行列です。ボードは9桁の数字で、各桁には3つの可能な値のいずれかがあります。0は空、1はx、2はoです。

ボードは単一の整数で設定できるため、このアプローチはミニマックスに最適です。マトリックスの形式は次のとおりです。

int suc[TOTAL][2]={ { 0, 10000}, { 1, 20001}, { 10, 20010}, { 12, 1012}, { 21, 1021},
    { 100, 20100}, { 102, 100102}, ...

ここで、数字の各ペアは、（a）現在の位置、および（b）、ミニマックスによって事前に計算された次に良い位置に対応します。したがって、ボードが空の場合（suc [0] [0] == 0）、次に適切な位置は、位置5、つまり中央（suc [0] [1] == 000010000）に「x」を配置することです。

実際、このプログラムでは、アドホックマトリックスで考えられるすべての回答がすでに計算されているため、ミニマックスを作成する必要はありません。次の動きを選択するための最も重要な機能は、suc（後続）マトリックスを調べるだけです。

/* find and return the next board after the given board terno */
int move(int terno)
{
    int i;

    for (i=0; i<TOTAL; i++)
        if (suc[i][0]==terno)
            return suc[i][1];
    return 0;
}

これは、量子アルゴリズム（および組み込みシステム）に適したアプローチです。これがお役に立てば幸いです。

気をつけて

于 2011-03-25T20:41:44.177 に答える