6

シンプルなミニマックスアルゴリズムで三目並べを解決しようとしています。シンプルですが、多くの言語をカバーする必要があります。私がこれまでに持っているもの：

ボードは、xまたはに設定された 9 つの (バインドされていない) 変数の配列として表されoます。

勝利条件は基本的に次のとおりwin(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player.です。8つのバリアントすべてについてetc. draw は、すべての変数がバインドされているかどうかの単純なチェックです。

move 句も単純です。これもmove(Player, [X|_], 0, 0) :- var(X), X=Player.すべての可能な位置に対してです (後のプログラムのためにコードの再利用を開いたままにします :) )。

これで、単純なバックトラッキングによってすべての可能な動きを生成できます。move(Player, Board, X, Y).これは、基本的にミニマックスに必要なものすべてです (明らかに、コンピューターが勝った場合は 1、引き分けの場合は 0、人間が勝った場合は -1 を返す単純なユーティリティ関数です)。簡単）。私はそれを実装する方法がわかりません。ネット上で見つけたすべての例はかなり複雑で、よく説明されていません。

私は n^2 またはそれより悪い実行時の動作で問題ないことに注意してください。これは実際には効率に関するものではありません。はい、私はLisp、Python、Javaでミニマックスを書く方法を知っています-そのコードをプロローグに「移植」する方法がわかりません。

4

1 に答える 1

2

さて、move/4 述語が既にあるので、可能なすべての動きを収集することから始めます。

findall(X-Y, move(Player, Board, X, Y), Moves)

あとは一手一手を評価するだけですよね？board_player_move_value/4そのために、ボードと特定のプレーヤーの動きが与えられたときに、その動きがこのプレーヤーにとってどれだけ良いかを判断するような述語を書きます。この段階で (他のプレイヤーにとって) 可能なさらなる動きに依存する可能性が高いのはこの述語であり、ここでミニマックスが発生します。たとえば、この手でゲームに勝った場合、それは良い手です。他のプレイヤーが次の手で勝つことができる場合、それは悪い手などです。この述語を使用して、Value-Move 形式の項のコレクションを作成し、keysort/2 を使用してそれらを並べ替え、手のうちの 1 つを選択します。ここで、「最良」は、最小化するプレーヤーまたは最大化するプレーヤーのどちらの動きを見つけようとしているかによって異なります。

于 2012-04-20T15:48:45.870 に答える