4

やあ！

チェス エンジン用の negamax 検索アルゴリズムを作成しようとしていますが、うまく動作しないようです。ウィキペディアの疑似コードを例として使用していますが、どういうわけか期待どおりの結果が得られません。プライ 2 で実行すると、ボードのデータ構造が変更されますが、そうすべきではありません。プライ 2 で関数の実行が終了した後、白 (または黒) のすべてのポーンは、開始位置から 2 スペース前方に移動します。

5 プライまで検索する非再帰関数でテストしたため、make および unmake move 関数は完全に機能しています。その後、それは完全に機能しました。negamax の実装に何か問題があるに違いありません。

ご助力ありがとうございます！

def negaMax(self, board, rules, ply, player):
        """ Implements a minimax algorithm. """
        if ply == 0:
            return self.positionEvaluation()

        self.max_eval = float('-infinity')

        self.move_list = board.generateMoves(rules, player)
        for self.move in self.move_list:
            board.makeMove(self.move, player)
            self.eval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player))
            board.unmakeMove(self.move, player)

            if self.eval > self.max_eval:
                self.max_eval = self.eval

        return self.max_eval
4

1 に答える 1

4

ここでの主な問題は、ローカル変数の代わりにオブジェクト変数を使用していると思います。

self.moveオブジェクト変数です。変更するたびに、再帰のすべてのレベルで変更が「認識」されます。これは通常、再帰アルゴリズムにとって悪いことです。

再帰アルゴリズムは自己完結型である必要があり、呼び出し環境に変更があったとしても最小限に抑える必要があります。これにより、アルゴリズムの流れを簡単に確認できます。

このコードで見られる 2 つの主な問題は次のとおりです。

  1. self.moveローカル変数にする必要があります ( として宣言しますmove)。後で行う場合: board.unmakeMove(self.move, player)- ボードが、再帰ツリーの奥深くに設定された別の手を元に戻しているのではないかと思いますが、意図したものではありません。ローカル変数を使用すると、この望ましくない動作が解消されます。
  2. 再帰呼び出しの各レベルは設定self.max_eval = float('-infinity')されているため、おそらくやりたいことではありませんが、常に変更します。

解決策は次のようになります。

def negaMax(self, board, rules, ply, player):
        """ Implements a minimax algorithm. """
        if ply == 0:
            return self.positionEvaluation()

        max_eval = float('-infinity')

        move_list = board.generateMoves(rules, player)
        for move in move_list:
            board.makeMove(move, player)
            currentEval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player))
            board.unmakeMove(move, player)

            if currentEval > max_eval:
                max_eval = currentEval 
        return max_eval

コード内のすべてが実際に解決されるとは 100% 確信が持てませんが (ただし、一部は解決されます)、オブジェクト変数を回避することで、コードの理解とデバッグがはるかに容易になることは 100% 確信しています。

于 2012-09-09T22:20:51.717 に答える