Я пишу движок изучения подкрепления, и я достиг контрольно-пропускного пункта.Сеть способна быстро обучаться на моей машине, но моя реализация game / mcts настолько медленная, что сети требуется несколько часов, чтобы сыграть несколько сотен игр против себя.Это делает процесс обучения невероятно медленным, поэтому я решил переписать игру с использованием битбордов.Это моя первая реализация перед переписыванием:
import numpy as np
def jump_generator(i, j, board, player, is_king, jumped):
d = -(-1)**(i%2)
no_move = True
for l in [player, -player][0:is_king+1]:
for k in [j+d,j]:
if -1 < i+2*l and i+2*l < 8:
if -1 < j+d*(-1)**(j == k) and j+d*(-1)**(j == k) < 4:
if board[i+l][k]*player < 0:
if board[i+2*l][j+d*(2*(j != k)-1)] == 0:
if not (i+l,k) in jumped:
no_move = False
for continuation in jump_generator(i+2*l,
j+d*(-1)**(j == k),
board,
player,
is_king,
jumped+[(i+l, k)]):
yield [(i+l, k)] + continuation
if no_move:
yield [(i, j)]
def move_generator(i, j, board, player, is_king):
d = -(-1)**(i%2)
no_move = True
for l in [player, -player][0:is_king+1]:
for k in [j+d,j]:
if -1 < i+l and i+l < 8:
if -1 < k and k < 4:
if board[i+l][k]*player == 0:
yield [(i, j), (i+l, k)]
no_move = False
if no_move:
yield [(i, j)]
class GameState():
def __init__(self, board, counter=None, legal=None, score=None):
self.board = board
self.turn = self.board[-1]
if legal == None:
moves = []
jumps = []
for i, row in enumerate(self.board[:-1]):
for j, square in enumerate(row):
if square*self.turn > 0:
for jump_seq in jump_generator(i, j, self.board[:-1], self.turn, square**2 > 1, []):
if len(jump_seq) > 1:
jumps.append([(i, j)]+jump_seq)
if not jumps:
for move in move_generator(i, j, self.board[:-1], self.turn, square**2 > 1):
if len(move) > 1:
moves.append(move)
if jumps:
legal = jumps
else:
legal = moves
legal = [tuple(a) for a in legal]
self.legal = legal
if counter == None:
counter = 0
self.counter = counter
if score == None:
if self.counter > 50:
score = 0
if not self.legal:
score = -self.turn
self.score = score
def next_board(self, move):
board = [list(row) for row in self.board[:-1]]
is_king = board[move[0][0]][move[0][1]]**2 > 1
if not is_king and 2*move[-1][0] == 7+7*self.turn:
board[move[-1][0]][move[-1][1]] = self.turn*2
else:
board[move[-1][0]][move[-1][1]] = board[move[0][0]][move[0][1]]
board[move[0][0]][move[0][1]] = 0
move = move[1:-1]
for square in move:
board[square[0]][square[1]] = 0
return tuple([tuple(row) for row in board])+(-self.turn,)
def next_state(self, move):
man_moved = self.board[move[0][0]][move[0][1]]**2 == 1
reset_counter = man_moved or len(move) > 2
return GameState(self.next_board(move), (not reset_counter)*(self.counter+1))
По сути, игра представлена в виде массива 4x8 с записями в диапазоне -2, -1, 0, 1, 2. Эти значения представляют разные частитипы и пустой квадрат.Вспомогательные функции jump_generator и move_generator принимают заданный квадрат (i, j) и возвращают список возможных шагов / захватов, которые возможны оттуда.Функция jump_function является рекурсивной для генерации принудительных последовательностей захватов.Объект игрового состояния инициализируется с массивом досок, откуда он генерирует легальные действия с использованием вспомогательных функций.Вот в основном это.У него также есть метод для генерации нового состояния из одного из его собственных законных действий.
Ниже приведена моя более новая реализация с использованием битбордов.2d-массив в предыдущем - это четыре 32-битных целых числа.Каждое целое число представляет тип фигуры, а двоичное целое представляет присутствие этого типа фигуры на доске.Доска закодирована умным способом, так что доступ к смежным с углом квадратам осуществляется простым вращением битов на фиксированное число для каждого «вектора движения».Существуют функции для этих битовых операций и постоянные целочисленные маски, которые кодируют квадраты, которые приводят к выходу за пределы для каждого «вектора» перемещения.Существует функция, которая принимает четыре плоскости (целые) и возвращает 8 плоскостей перемещения.Все это делается с помощью битовой логики на np.uint32.Я даже использовал некоторые памятки.Наконец, эти плоскости «повторяются» с помощью битовых сдвигов, чтобы найти правильные ходы и сгенерировать результирующую позицию.
import numpy as np
int32 = np.uint32
int8 = np.uint8
zero = int32(0)
one = int32(1)
def rot(b, n):
n %= 32
n = int32(n)
return (b >> n) | (b << (int32(32)-n))
def reverse(b):
r = zero
for i in range(32):
r = r << one
if b & one:
r = r ^ one
b = b >> one
return r
def swap(b):
return reverse(rot(b, int32(20)))
masks_move = (~int32(2**1 + 2**5 + 2**9 + 2**11 + 2**17 + 2**25 + 2**31),
~int32(2**2 + 2**5 + 2**10 + 2**11 + 2**18 + 2**25 + 2**26 + 2**31),
~int32(2**0 + 2**1 + 2**6 + 2**9 + 2**12 + 2**17 + 2**18 + 2**25),
~int32(2**0 + 2**2 + 2**6 + 2**10 + 2**12 + 2**18 + 2**26))
masks_jump = (~int32(2**0 + 2**4 + 2**8 + 2**10 + 2**16 + 2**24 + 2**30),
~int32(2**3 + 2**4 + 2**19 + 2**24 + 2**27 + 2**30),
~int32(2**7 + 2**8 + 2**13 + 2**16 + 2**19 + 2**24),
~int32(2**1 + 2**3 + 2**7 + 2**11 + 2**13 + 2**19 + 2**27))
masks = masks_move + masks_jump
promote = ~int32(2**5 + 2**11 + 2**25 + 2**31)
def move_boards(m1, k1, m2, k2):
ally = m1 | k1
enemy = m2 | k2
every = ally | enemy
enemy_0 = rot(enemy, one)
enemy_4 = rot(enemy_0, one)
enemy_1 = rot(enemy_4, int32(5))
enemy_5 = rot(enemy_1, int32(7))
enemy_7 = rot(enemy_5, int32(4))
enemy_2 = rot(enemy_7, int32(7))
enemy_6 = rot(enemy_2, int32(5))
enemy_3 = rot(enemy_6, one)
ally_0 = rot(ally, one)
ally_4 = rot(ally_0, one)
ally_1 = rot(ally_4, int32(5))
ally_5 = rot(ally_1, int32(7))
ally_7 = rot(ally_5, int32(4))
ally_2 = rot(ally_7, int32(7))
ally_6 = rot(ally_2, int32(5))
ally_3 = rot(ally_6, one)
board0 = ally & ~(ally_0 | enemy_0) & masks[0]
board1 = ally & ~(ally_1 | enemy_1) & masks[1]
board2 = ally & ~(ally_2 | enemy_2) & masks[2]
board3 = ally & ~(ally_3 | enemy_3) & masks[3]
board4 = ally & enemy_0 & ~ally_4 & masks[0] & masks[4]
board5 = ally & enemy_1 & ~ally_5 & masks[1] & masks[5]
board6 = ally & enemy_2 & ~ally_6 & masks[2] & masks[6]
board7 = ally & enemy_3 & ~ally_7 & masks[3] & masks[7]
return (board0, board1, board2, board3, board4, board5, board6, board7)
def actions(m1, k1, m2, k2):
boards = move_boards(m1, k1, m2, k2)
every = zero
actions = []
for b, board in enumerate(boards):
every |= board
place = one
for i in range(32):
if place & every == place:
for b, board in enumerate(boards):
if place & board == place:
actions.append((i,b))
place <<= one
return actions
Я протестировал обе, выкрутив их в конечное состояние тысячу раз подряд.Первая реализация делала это в 3-4 раза быстрее.Это казалось правдой для сколь угодно многих игр.