Python — Как бороться с очень большими битбордами

Я работаю над настольной игрой для 2 игроков (например, подключить 4), с параметрическим размером платы час, вес. Я хочу проверить состояние выигрыша, используя HW-размер битбордов.

В таких играх, как шахматы, где размер платы фиксирован, битборды обычно представлены с каким-то 64-битным целым числом. когда час а также вес не являются постоянными и, может быть, очень большими (допустим, 30 * 30) — это хорошая идея для битбордов? Если да, то есть ли какие-либо типы данных в C / C ++ для работы с большими битбордами, сохраняющими свою производительность?

Поскольку я сейчас работаю над Python, решение на этом языке тоже ценится! 🙂

заранее спасибо

0

Решение

Я написал этот код недавно, чтобы поиграть с концепцией игры. Там нет интеллектуального поведения. просто случайные ходы, чтобы продемонстрировать игру. Я думаю, это не важно для вас, поскольку вы ищете только быструю проверку условий выигрыша. Эта реализация быстра, поскольку я старался избегать циклов for и использовать только встроенные функции python / numpy (с некоторыми хитростями).

import numpy as np

row_size = 6
col_size = 7
symbols = {1:'A', -1:'B', 0:' '}

def was_winning_move(S, P, current_row_idx,current_col_idx):
#****** Column Win ******
current_col = S[:,current_col_idx]
P_idx= np.where(current_col== P)[0]
#if the difference between indexes are one, that means they are consecutive.
#we need at least 4 consecutive index. So 3 Ture value
is_idx_consecutive = sum(np.diff(P_idx)==1)>=3
if is_idx_consecutive:
return True

#****** Column Win ******
current_row = S[current_row_idx,:]
P_idx= np.where(current_row== P)[0]
is_idx_consecutive = sum(np.diff(P_idx)==1)>=3
if is_idx_consecutive:
return True

#****** Diag Win ******
offeset_from_diag = current_col_idx - current_row_idx
current_diag = S.diagonal(offeset_from_diag)
P_idx= np.where(current_diag== P)[0]
is_idx_consecutive = sum(np.diff(P_idx)==1)>=3
if is_idx_consecutive:
return True
#****** off-Diag Win ******
#here 1) reverse rows, 2)find new index, 3)find offest and proceed as diag
reversed_rows = S[::-1,:] #1
new_row_idx = row_size - 1 - current_row_idx #2
offeset_from_diag = current_col_idx - new_row_idx #3
current_off_diag = reversed_rows.diagonal(offeset_from_diag)
P_idx= np.where(current_off_diag== P)[0]
is_idx_consecutive = sum(np.diff(P_idx)==1)>=3
if is_idx_consecutive:
return True
return False

def move_at_random(S,P):
selected_col_idx = np.random.permutation(range(col_size))[0]
#print selected_col_idx
#we should fill in matrix from bottom to top. So find the last filled row in col and fill the upper row
last_filled_row = np.where(S[:,selected_col_idx] != 0)[0]
#it is possible that there is no filled array. like the begining of the game
#in this case we start with last row e.g row : -1
if last_filled_row.size != 0:
current_row_idx = last_filled_row[0] - 1
else:
current_row_idx = -1
#print 'col[{0}], row[{1}]'.format(selected_col,current_row)
S[current_row_idx, selected_col_idx] = P
return (S,current_row_idx,selected_col_idx)

def move_still_possible(S):
return not (S[S==0].size == 0)

def print_game_state(S):
B = np.copy(S).astype(object)
for n in [-1, 0, 1]:
B[B==n] = symbols[n]
print B

def play_game():
#initiate game state
game_state = np.zeros((6,7),dtype=int)
player = 1
mvcntr = 1
no_winner_yet = True
while no_winner_yet and  move_still_possible(game_state):
#get player symbol
name = symbols[player]

game_state, current_row, current_col = move_at_random(game_state, player)
#print '******',player,(current_row, current_col)
#print current game state
print_game_state(game_state)
#check if the move was a winning move
if was_winning_move(game_state,player,current_row, current_col):
print 'player %s wins after %d moves' % (name, mvcntr)
no_winner_yet = False

# switch player and increase move counter
player *= -1
mvcntr +=  1
if no_winner_yet:
print 'game ended in a draw'
player = 0
return game_state,player,mvcntr

if __name__ == '__main__':
S, P, mvcntr =  play_game()

дайте мне знать, если у вас есть какие-либо вопросы

ОБНОВИТЬ: Объяснение:

При каждом движении посмотрите на столбец, строку, диагональ и вторичную диагональ, которая проходит через текущую ячейку, и найдите последовательные ячейки с текущим символом. Избегайте сканирования всей доски.

введите описание изображения здесь

извлечение клеток в каждом направлении:

колонка:

current_col = S[:,current_col_idx]

строка:

current_row = S[current_row_idx,:]

Диагональ:
Найти смещение желаемой диагонали от
главная диагональ:

diag_offset = current_col_idx - current_row_idx
current_diag = S.diagonal(offset)

внедиагональная:

Переверните строки матрицы:

S_reversed_rows = S[::-1,:]

Найти индекс строки в новой матрице

new_row_idx = row_size - 1 - current_row_idx
current_offdiag = S.diagonal(offset)

введите описание изображения здесь

1

Другие решения