tic-tac-toeのミニマム

Question

シンプルミニマックスアルゴリズムでtic-tac-toeを解決しようとしています。シンプルですが、多くの言語をカバーする必要があります。

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

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

move句も簡単です：move(Player, [X|_], 0, 0) :- var(X), X=Player.、可能なすべての位置について（私は後でプログラムでコードを再利用しています:)）。

私はminimaxのために基本的に必要なすべてのものであるべきであるmove(Player, Board, X, Y).です（明らかに、コンピュータが勝った場合は1を返し、描画の場合は0を返す単純なユーティリティ関数です。if人間が勝つ、それは簡単です）。私はそれをどのように実装するのか分かりません。ネット上にあるすべての例はかなり複雑でよく説明されていません。

注意n^2以上の実行時の動作には問題ありません。効率的ではありません。そして、私はlisp、python、javaでミニマイズを書く方法を知っています - プロローグにそのコードを "移植"する方法はまったくありません。

Answer 1

さて、あなたはすでにあなたの移動/ 4述語を持っているように、私は可能なすべての動きの収集で始まります：

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

をそして、それは単に各移動を評価する問題だ、ではありませんそれ？そのためには、ボードと与えられたプレイヤーの移動を考慮して、このプレーヤーの動きがどれほど良いかを決定する述語、board_player_move_value/4を書きます。この段階では（他のプレイヤーにとって）可能なさらなる動きに依存する可能性が高いのはこの述語であり、これはミニマックスが行われる場所です。たとえば、この動きがゲームに勝った場合、それは良い動きです。他のプレイヤーが次の移動で勝つことができれば、それは悪い動きなどです。この述語を使用してValue-Moveという形式の用語集を構築し、keysort/2を使用してそれらをソートし、 「最高」は、私が最小化するプレーヤーか最大化するプレーヤーの動きを見つけようとしているかどうかによって決まります。