Генерация ходов в Отелло с помощью битбордов - PullRequest
Новая
       66

Генерация ходов в Отелло с помощью битбордов

1 голос
/ 26 января 2020

Я сделал два очень похожих ИИ Отелло. В первом случае плата представлена ​​в виде массива длиной 100, где плата 8x8 представлена ​​«серединой» платы, а остальные - это буферные пространства по краю (индекс 11 - верхний левый угол платы 8x8, индекс 88 - нижний правый угол). Чтобы сделать ход в позиции index, я использую следующий код 

changed = [index]

for direction in (1, 9, 10, 11):
    shift = index-direction
    while board[shift] == opp:
        shift -= direction
    if board[shift] == player:
        changed += [*range(shift+direction, index, direction)]

for direction in (1, 9, 10, 11):
    shift = index+direction
    while board[shift] == opp:
        shift += direction
    if board[shift] == player:
        changed += [*range(index+direction, shift, direction)]

. Для генерации ходов я затем go просматривает возможные индексы (должен быть внутренним 8x8, и этот тайл пуст) и проверьте, если len(changed) > 1. Если это так, я устанавливаю элементы board в changed на player.

Во втором ИИ (который, как я надеялся, будет быстрее делать ходы), доска представляется в виде двух 64-битные битборды - один для игрока, стремящегося максимизировать счет, и другой для игрока, пытающегося минимизировать счет. Чтобы сделать ход, я использую тот же код, что и [здесь] (https://www.hanshq.net/othello.html#moves), только что преобразованный в Python. 

new_disk = 1 << index
captured = 0
newmy_disks = my_disks|new_disk

for direction in range(8):
    x = shift(new_disk, direction) & opp_disks

    for i in range(5):
        x |= shift(x, direction) & opp_disks

    bounding_disk = shift(x, direction) & my_disks
    if bounding_disk != 0:
        captured_disks |= x

newmy_disks = newmy_disks^captured_disks
newopp_disks = opp_disks^captured_disks

С представлением на битовой доске, играя в 1000 случайных игр занимает около 7 секунд, в то время как представление массива занимает 4 секунды.

Мои вопросы: Как я могу ускорить представление битовой доски при выполнении шагов? Можно ли одновременно проверить возможные ходы и вернуть новые битборды?

...