Minimaxは馬鹿について説明しました
https://stackoverflow.com/questions/3956258
-
08-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Minimaxアルゴリズムを使用して、無敵のテクチャクトAIを作成しようとして一日中無駄にしました。途中で何かを逃した（脳を揚げた）。
私はここでコードを探しているのではなく、私がどこで間違ったのかをよりよく説明しています。
現在のコードは次のとおりです（Minimaxメソッドは常に何らかの理由で0を返します）：
from copy import deepcopy
class Square(object):
def __init__(self, player=None):
self.player = player
@property
def empty(self):
return self.player is None
class Board(object):
winning_combos = (
[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6],
)
def __init__(self, squares={}):
self.squares = squares
for i in range(9):
if self.squares.get(i) is None:
self.squares[i] = Square()
@property
def available_moves(self):
return [k for k, v in self.squares.iteritems() if v.empty]
@property
def complete(self):
for combo in self.winning_combos:
combo_available = True
for pos in combo:
if not pos in self.available_moves:
combo_available = False
if combo_available:
return self.winner is not None
return True
@property
def player_won(self):
return self.winner == 'X'
@property
def computer_won(self):
return self.winner == 'O'
@property
def tied(self):
return self.complete == True and self.winner is None
@property
def winner(self):
for player in ('X', 'O'):
positions = self.get_squares(player)
for combo in self.winning_combos:
win = True
for pos in combo:
if pos not in positions:
win = False
if win:
return player
return None
@property
def heuristic(self):
if self.player_won:
return -1
elif self.tied:
return 0
elif self.computer_won:
return 1
def get_squares(self, player):
return [k for k,v in self.squares.iteritems() if v.player == player]
def make_move(self, position, player):
self.squares[position] = Square(player)
def minimax(self, node, player):
if node.complete:
return node.heuristic
a = -1e10000
for move in node.available_moves:
child = deepcopy(node)
child.make_move(move, player)
a = max([a, -self.minimax(child, get_enemy(player))])
return a
def get_enemy(player):
if player == 'X':
return 'O'
return 'X'
解決
あなたの完全な関数は期待どおりに機能していないため、何かが起こる前にゲームを結び付けられると宣言されます。たとえば、このセットアップを考慮してください。
>> oWinning = {
1: Square('X'),
3: Square('O'), 4: Square('X'),
6: Square('O'), 8: Square('X'),
}
>> nb = Board(oWinning)
>> nb.complete
True
>> nb.tied
True
これは、次の動きでコンピューターにとって勝利となるはずです。代わりに、ゲームが結びついていると言います。
問題は、現在、あなたの論理が現在、コンボ内のすべての正方形が無料かどうかを確認することです。それらのいずれかがそうでない場合、そのコンボを勝ち取ることができないと想定しています。その必要なことは、そのコンボのポジションが占有されているかどうかを確認することです。これらのコンボがすべてまたは同じプレーヤーのいずれかである限り、そのコンボはまだ利用可能であると見なされるべきです。
例えば
def available_combos(self, player):
return self.available_moves + self.get_squares(player)
@property
def complete(self):
for player in ('X', 'O'):
for combo in self.winning_combos:
combo_available = True
for pos in combo:
if not pos in self.available_combos(player):
combo_available = False
if combo_available:
return self.winner is not None
return True
更新されたコードでこれを適切にテストしたので、このテストケースで期待される結果が得られます。
>>> nb.minimax(nb, 'O')
-1
>>> nb.minimax(nb, 'X')
1
他のヒント
ステップ1：ゲームツリーを構築します
現在のボードから始めることで、相手ができるすべての可能な動きを生成します。次に、それらのそれぞれについて、あなたができるすべての可能な動きを生成します。 tic-tac-toeの場合、誰もプレイできないまで続けます。他のゲームでは、通常、特定の時間または深さの後に停止します。
これは木のように見え、紙の一部に自分で描き、現在のボードの上に、すべての対戦相手が下の1つのレイヤーを移動します。
ステップ2：ツリーの下部ですべてのボードを獲得する
Tic-Tac-Toeのような単純なゲームでは、負けた場合、50タイ、100勝を挙げればスコア0になります。
ステップ3：ツリーのスコアを伝播します
これは、MIN-MAXが出てくる場所です。以前はないボードのスコアは、その子供と誰がプレーするかによって異なります。あなたとあなたの対戦相手の両方が、与えられた状態で常に可能な限り最高の動きを選択すると仮定します。対戦相手にとって最良の動きは、与える動きです 君 最悪のスコア。同様に、あなたの最良の動きは、最高のスコアを与える動きです。対戦相手のターンの場合、最小スコアで子供を選択します（それは彼の利益を最大化します）。それがあなたの番である場合、あなたはあなたが可能な限り最高の動きをすると仮定するので、あなたは最大を選択します。
ステップ4：最高の動きを選択してください
現在、現在のポジションから可能なすべてのプレーの中で最高の伝播スコアをもたらす動きをプレイします。
空白のボードから始めることがあまりにも多すぎる場合は、高度なTIC-TAC-Toeポジションから始める場合は、一枚の紙で試してみてください。
再帰の使用：非常に多くの場合、これは再帰を使用することで簡素化できます。 「スコアリング」関数は、各深さで再帰的に呼ばれ、深さが奇妙なかどうかに応じて、それぞれすべての可能な動きに対して最大またはminを選択します。動きが不可能な場合、ボードの静的スコアを評価します。再帰ソリューション（例：コードの例）は、把握するのが少し難しい場合があります。
あなたがすでに知っているように、Minimaxのアイデアは、対戦相手が常に最悪の価値で動きをプレイすると仮定して、最高の価値を深く検索することです（私たちにとって最悪なので、彼らにとって最良です）。
アイデアは、各位置に価値を与えようとするということです。あなたが失う位置は否定的であり（私たちはそれを望んでいません）、あなたが勝つポジションは前向きです。あなたは常に最高値の位置を試してみると仮定しますが、相手は常に最悪の結果をもたらす最低値の位置を常に目指していると仮定します。だからあなたは彼らの靴に身を置き、あなたが彼らと同じくらい良いプレイをしてみてください、そして彼らがそれをすると仮定します。
したがって、2つの動きが可能であることがわかった場合、1つは勝つか負けるかを選択できます。したがって、引き分けに行く方が良いです。
より「アルゴリズム」ビューのために。
2つの可能な位置を除いて、グリッドがほぼいっぱいであると想像してください。
最初のものをプレイしたときに何が起こるかを考えてください。
相手がもう一方を演奏します。それは彼らの唯一の可能な動きであるため、彼らからの他の動きを考慮する必要はありません。結果を見て、結果の値を関連付けます（ +∞がwon、0の場合は0、失われた場合：tic tac toeの場合、それらを+1 0および-1として表すことができます）。
次に、2番目のものをプレイしたときに何が起こるかを考えてください。
（ここでも、対戦相手には1つの動きのみがあり、結果の位置を見て、位置を評価します）。
2つの動きを選択する必要があります。それが私たちの動きなので、私たちは最高の結果を望んでいます（これはミニマックスの「最大」です）。 「最高の」動きとして、より高い結果を持つものを選択してください。それは、「終わりからの2つの動き」の例のためです。
今、あなたは2つではなく3つの動きが残っていると想像してください。
原則は同じです。3つの可能な動きのそれぞれに値を割り当てて、最適なものを選択できるようにする必要があります。
したがって、3つの動きの1つを検討することから始めます。
あなたは現在、上記の状況にあり、可能なのは2つの動きだけですが、それは相手の番です。次に、上記のように、相手の可能な動きの1つを検討し始めます。同様に、可能な各動きを見て、両方の結果の値を見つけます。それは対戦相手の動きなので、彼らが私たちにとって最悪の投票率を持つものである「最高の」動きをプレイすると仮定します。もう一方を無視します。とにかくあなたが見つけたものが彼らにとって最適だったと彼らがプレイすると仮定します。これがあなたの動きがもたらすものであるため、3つの動きの最初に割り当てる価値です。
これで、他のそれぞれの可能な2つの動きを検討します。同じ方法で価値を与えます。そして、3つの動きから、最大値のある動きを選択します。
次に、4つの動きで何が起こるかを考えます。 4つの動きのそれぞれについて、相手の3つの動きに対して何が起こるかを見て、それぞれについて、あなたはあなたのために残っている2つの動きの中で最悪の結果を与えるものを選択すると仮定します。
これがどこに向かっているのかわかります。最後から移動nステップを評価するには、n可能な動きごとに何が起こるかを見て、最高のものを選ぶことができるように値を与えようとします。その過程で、N-1：The Optonerでプレーするプレイヤーに最適な動きを見つけて、値を下回るステップを選択する必要があります。 N-1移動を評価する過程で、私たちのものとなる可能性のあるN-2移動を選択する必要があります。このステップでできる限りプレイすると仮定します。等。
これが、このアルゴリズムが本質的に再帰的である理由です。 N-1ですべての可能なステップを評価するn、n-1で何でも。すすぎ、繰り返します。
TIC-TAC-Toeの今日のマシンは、ゲームの開始からすぐに可能なすべての結果を計算するのに十分なほど強力です。より複雑なゲームのためにそれを実装しようとするとき、それは時間がかかりすぎるので、ある時点でコンピューティングを停止する必要があります。したがって、複雑なゲームの場合、可能なすべての次の動きを探し続けるか、今すぐポジションに値を与えて早めに戻そうとするかどうかを決定するコードを書く必要があります。つまり、最終的ではない位置の価値を計算する必要があることを意味します - たとえば、各相手がボード上に持っている資料の量、仲間なしでチェックの即時の可能性、あなたが制御するタイルの数、すべて、それは些細なことではありません。
