The most efficient valid move generation for minimax

Oct 15 2020

Problem

I am creating a chess engine in Python using Minimax algorithm (with alpha/beta pruning) but I have some issues with performance. Currently the thinking time looks something like this for a mid game position:

Depth 1: 0.01 s
Depth 2: 0.07 s
Depth 3: 0.76 s
Depth 4: 19.8 s

I have timed each function and here are the worst performing functions, time is per move at depth 4:

get_valid_moves (10 s)
deepcopy (8 s)
get_all_possible_moves (8 s)

What I have tried

I have tried to have the board represented as a 2D array (8x8) which is the easiest solution. With a 1D representation (10x12) I got a tiny bit better performance but not enough to increase depth.

What I need feedback on

転置テーブルルックアップなどでミニマックス関数を最適化しようとする前に、有効な移動とすべての移動を計算する最も効率的な方法があることを望んでいました。現在使用しているプロセスは次のとおりです。

キングの場所から8方向をループして、チェックしているかどうか、どの部分が固定されているかを確認します（8x8ループ）
チェックやピンを考慮せずにすべての可能な（疑似？）移動を取得します（8x8ループでボード上のすべてのピースを見つけてから、可能な各ピースをリストに追加します）
私がチェックしているか、ダブルチェックしているかを確認して、有効な移動を取得します（合法でない場合は、all_possible_movesリストから移動を削除します）

これは、私が作品、この場合はビショップの可能な動きを計算する方法の例です：

def get_bishop_moves(self, row, col, moves):
    piece_pinned = False
    pin_direction = ()
    for i in range(len(self.pins)-1, -1, -1):
        if self.pins[i][0] == row and self.pins[i][1] == col:
            piece_pinned = True
            pin_direction = (self.pins[i][2], self.pins[i][3])
            self.pins.remove(self.pins[i])
            break

    directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
    enemy_color = 'b' if self.is_white_turn else 'w'
    for d in directions:
        for i in range(1, 8):
            end_row, end_col = row + d[0] * i, col + d[1] * i
            if all(0 <= x <= 7 for x in (end_row, end_col)):
                if not piece_pinned or pin_direction == d or pin_direction == (-d[0], -d[1]):
                    end_piece = self.board[end_row][end_col]
                    if end_piece == '--':
                        moves.append((row, col), (end_row, end_col))
                    elif end_piece[0] == enemy_color:
                        moves.append((row, col), (end_row, end_col))
                        break
                    else:
                        break
            else:
                break

ボードの2D表現：

start_board = np.array([
            ['bR', 'bN', 'bB', 'bQ', 'bK', 'bB', 'bN', 'bR'],
            ['bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp'],
            ['--', '--', '--', '--', '--', '--', '--', '--'],
            ['--', '--', '--', '--', '--', '--', '--', '--'],
            ['--', '--', '--', '--', '--', '--', '--', '--'],
            ['--', '--', '--', '--', '--', '--', '--', '--'],
            ['wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp'],
            ['wR', 'wN', 'wB', 'wQ', 'wK', 'wB', 'wN', 'wR']])

最後の質問

（ビットボードを使用せずに）有効な移動生成を別の方法で行う方法はありますか？私は何かを見落としていますか？エンジンが深さ4を超えないときに評価関数を操作するのは楽しいことではありません... :)

回答

1 Noname Oct 16 2020 at 18:15

ボトルネックがどこにあるかを把握した後で停止するのではなく、ボトルネックを特定し続ける必要があります。たとえば、毎回get_xxxx_moves（）を呼び出しますか？

あなたがするチャンスに：

毎回すべての移動を一覧表示する代わりに、移動の影響を受けるピース移動リストを更新するだけで、必要な作業を減らすことができる場合があります。他の部分（ステータスと有効な移動リスト）は影響を受けず、再計算する必要はありません。

したがって、オープニングムーブe2-e4は、開始マスe2（wQ、wK、wBf1、およびwNg1）をカバー/攻撃するピースにのみ影響するため、必要な再計算はこれらだけです。e4をカバー/攻撃するものはないので、今はこれ以上作業する必要はありません。