私はMinimaxを使用してコンピュータの接続を再生させています6。アルゴリズムの高速化のためにAlpha-Betaプルーニングも使用しています。転置テーブル？
転置テーブルを追加してアルゴリズムをさらに高速化したいと考えています。私は彼らの経験が全くありません。
誰かが転位テーブルの基本について説明し、Connect 6のようなゲームにどのように適用することができますか？有用なリソースへのリンクはうまくいくでしょう。
I」のハッシュテーブルに精通メートル
私が見つけたもの：。！
）http://chessprogramming.wikispaces.com/Transposition+Table
リンクは転置テーブルの良い説明を与えるが、完全に図のようにそのハードので、チェスに焦点を当てて
最初にミニマックスアルゴリズムを適用すると、あなたができるボードの位置ごとに（ミニマックスの意味で）最良のプレーを計算する必要があります将来はうずくまる。アルファベータプルーニングは、不要な計算を減らすのに役立ちます。なぜなら、決して特定の動きをするつもりがないことを知っていれば、その動きを再生する価値を計算する必要がないからです。
いくつかのゲームでは、特定のボードでの最善のプレーは、その時点でのボードの状態によって完全に決めることができます。チェスはこのようなものなので、他にもいくつかのゲームがあります。重要なことは、特定のゲーム状態にどのように到達したかは、その状態になってからは、（ミニマックスの視点からは）重要ではないということです。
特に、単語のチェスセンスの転位は、開始位置から終了位置に移動するために2つの異なる移動経路をとるときに起こることです。
転置テーブルを使用すると、異なる再生がボードが同じエンドステートになるという状況に遭遇したときに最適な移動の計算を最適化することができます。基本的に1つの特定のボード位置に到達すると、ミニマックス計算の結果を転置テーブルのその位置に保存するだけです。これは、後で別の動きのリストが同じボードに到着した場合に、突然、そのボードのミニマックスを完全に再計算する必要はないということです。転置テーブル
プレイヤーが同じボード位置に到着したプレイ方法が複数ある場合は、その計算結果を保存することができる場合は、ゲームツリーのその枝を2度以上見て複製する必要はありませんどういうわけか。これを効率的に行うには、基板の位置を効率的に表現できるようにする必要があります。次に、転置テーブルでボードの位置をすばやく参照できるようにするデータ構造が必要です。正しい表現を見つけることは、あなたが分析しているゲームに大きく依存します。
connect6 is this gameは、おそらく例が良いでしょう場合：
は、ボードは、この（位置A）のように起動すると言う：
X 0
0 X
（位置Bにあなたを取得する動きの複数のセットがあります）：
X 0 0 0
0 X X X
0 X
がありますnは位置Aから位置Bに行くの方法あなたはこれについて行けば、単純にあなたがpositioで最善手を見つけるためにテストする必要がありますと言いますn Bまでn回（ツリーのどの枝がアルファベットプルーンオフになるかに依存する）。しかし、実際にはBと同じくらい同じ数字のの計算をBボードの位置に対して何度も行う必要がなければ、本当にうまくいくでしょう。
このアイデアを活用するために必要なことは、接続ボードの位置を表す方法を見つけることです。ボードを表現できる方法の1つは、Nがボードのディメンションであり、空の場合に対応する各セルの列挙値を格納するか、Xを持つか、または0を持つだけです。N by N配列を持つことです。しかし、この素朴なアプローチは、私たちが常にこれらの厄介な配列を渡しているので、位置を探すための大きな特性を持っていません。N by N配列。言うまでもなく、これらの多くの配列を常に格納しなければならないことは、大量のメモリを必要とします。
したがって、N by Nボードを使用し、処理オーバーヘッドをかけずにほぼ一意の整数にマップするハッシュ関数を定義できれば、このプロセスを合理化することができます。ボードをハッシュし、それがテーブルの中にあるかどうかを見れば、このように速くなるはずです。
これは、人々が分析している特定のゲームに対してハッシュ関数を作成しようとする理由です。接続6の場合、私は最良のハッシング関数が何であるか分かりません。それはあなたが解決しなければならないものです。
このようなことから最高のパフォーマンスを得るには、いろいろな手間がかかりますが、うまくいけば、このポストはあなたにいくつかのアイデアを与えました。あなたが私に何かを広げたいと思ったらコメントしてください。
This MediocreChessの記事では、転置テーブルについて詳しく説明しています。 Zobrist algorithmは転置テーブルを作成するのが非常に簡単です。
二つの単語でzobristシステム：
これは、作品を削除することができます非常に良いシステムです！同じ番号をもう一度XORする必要があります。ネガマックス/アルファベータアルゴリズムは、状態を頻繁に変更/復元する必要があるため、本当に便利です。 Zobristのキーを最新の状態に維持するのは簡単です。
転置テーブルのシステムである：特定のゲーム位置の
しかし、おそらく2^32または2^64エントリを保存したくないので、Zobristキーの "ハッシュ"を取って転置テーブルのエントリを制限してみましょう。 16のゲームポジション（実際はおそらく> 2^20）です。このハッシュを取得するには、簡単な方法が「モジュロ」zobristキー、または「バイナリおよび」を行うです：あなたは0との間の整数を得る= zobrist_key & 0xFFFFの
移調テーブルインデックス2^16-1、これは転置テーブルのインデックスです！ もちろん、衝突が発生する可能性があるので、完全なzobristキーを転置テーブルに格納することができます。指定された位置のために
はのは、まとめてみましょう。重要なデータをscore、best_move、zobrist_key、flag、depthのテーブルエントリに保存しましょう。
ので接続6のために、あなたは、2石の色を持っている、とのは59x59ポジションを言わせて、あなたは59x59x2 = 6962乱数の配列を作成する必要があります。 Zobristキーでゲーム位置をエンコードするには、それぞれの石を取って、その色とその位置について、生成した数字を取り出してXORします。 Zobrist Keyをインデックス（ハッシュ、バイナリ "and"、...）に変換し、転置テーブルのこのインデックスにデータを格納します。
大変感謝しています！ :) – dfg