4

Python コーディング クラスのプロジェクトを書いていますが、質問があります。私は、ゲームで数手先を見て、最適と思われる手を選択するリバーシエンジンを作成しています。Python がこれに理想的な言語ではないことは理解していますが (他の言語ほど高速ではないため)、少なくとも機能するコードを書くことは可能だと思いますが、それでも少し遅いかもしれません。

そうは言っても、ゲーム ボード (マトリックスと考えてください) と整数を保持するゲーム ツリーの 2 つのテーブルを作成しようとしています。エントリを追加、削除、および読み取るために、メモリ効率が高く高速なものを使用したいと考えています。

私が現在使用しているボードはあまり効率的ではありません。これと同等でメモリを軽くするものを作成するために、誰かが提案するモジュール (使用方法の説明付き) を尋ねたいと思いました (例: 配列、numpy。ただし、どちらの使用方法もわかりません)。これらは）：

self.board = [[0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 1, 2, 0, 0, 0,],
              [0, 0, 0, 2, 1, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,]
              [0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,]]

ゲーム ツリーについては、リストのリストをどれだけ軽量にするかによってアイデアがあります。私が取り組んでいる標準の python で書かれたアイデアは次のようになります。

tree_zero = %

tree_one =  [%, %, %]

tree_two = [[%, %, %], [%, %, %], [%, %, %]]

tree_thre = [[[%, %, %], [%, %, %], [%, %, %]],
             [[%, %, %], [%, %, %], [%, %, %]],
             [[%, %, %], [%, %, %], [%, %, %]]],

tree_four = [[[[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]]],

             [[[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]]],

             [[[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]]]]

各 % は上記のボードの 1 つになります (理想的ではありません: すべてのターンに正確に 3 つのオプションがあるわけではありません)。しかし、これは遅くて重いオブジェクトであり、Python がメモリを効率的に使用するのは困難です (特に、4 プライより深くする場合)。

誰かが以前にこのようなプログラムを扱ったことがある場合、またはインポートする効率的なモジュールのアイデアを持っている場合は、私に知らせてください!

ゲーム ツリーの例として、ウィキペディアのページ、特にページの最初の画像を考えてみてください。

編集: 理想的には、4 手先より先を見たいと思います。これは、最初の 4 つのレベルがどのように見えるかの単なる例です。また、指定されたツリーの複数のコピーが使用のために浮かんでいます。このように指数関数的に成長するものには、スピードが重要です。

4

1 に答える 1

3

私の意見では、Python はこの種の作業に完全に最適です! つまり、Python を使用してボード ゲームの AI を作成するのは、非常に楽しく生産的な時間を過ごしました。

私の最初の推奨事項は、ビットボードを探索することです。ここでの適用例はチェス用ですが、コンセプトは完全にリバーシに適用できます。0 と 1 を使用してセット サイズのボード上のピースの存在を表すと、メモリ フットプリントが小さくなるという利点があるだけでなく、計算速度が向上するという利点もあります (ビット演算は等値演算よりも高速です)。

さらに、何らかの方法で再帰を実装するようにモデルを再設計する必要があります (スコアリング関数によって促進されます)。このような実装は、1、2、3、4 移動のロジックを予測してハードコーディングするのではなく、単一の関数を記述して無限の移動深度 (または、設計によって無制限で、リソースによってのみ制限される) をスケーリングできることを意味します。 . この効果に対して適切に設計された関数は、両方の側 (プレイヤー) に対して機能し、しきい値内に収まる最適なオプションを選択するために停止できます (選択した任意の基準によって停止され、計算された位置/リアルタイムで費やされます)。

参考までに、あなたのプログラムとほぼ同じ要件で作成したThudというボード ゲームの github を次に示します。ここでは、17x17 のボード、3 つの異なるピース、および 2 つの異なる戦略を使用しました。これは、リバーシのルールよりも複雑であることがわかります。

おっと、優れた再帰モデルはマルチスレッドにも対応しています!

于 2012-04-12T20:19:20.087 に答える