Как работать с очень большим Bitboards

Question

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

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

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

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

Answer 1

Я написал этот код, а назад просто играть с концепцией игры. Существует не разумное поведение. просто случайные шаги, чтобы продемонстрировать игру. Я думаю, это не важно для вас, так как вы ищете быстрый контроль условий выигрыша. Эта реализация выполняется быстро, так как я сделал все возможное, чтобы избежать циклов и использовать только встроенные функции 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() 

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

UPDATE: Объяснение:

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

добывающие клеток в каждом направлении:

колонка:

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)