How to deal with very big Bitboards

Question

I'm working on a 2-player board game (e.g. connect 4), with parametric board size h, w. I want to check for winning condition using hw-sized bitboards.

In game like chess, where board size is fixed, bitboards are usually represented with some sort of 64-bit integer. When h and w are not constant and maybe very big (let's suppose 30*30) are bitboards a good idea? If so, are the any data types in C/C++ to deal with big bitboards keeping their performances?

Since I'm currently working on python a solution in this language is appreciated too! :)

Thanks in advance

In C or in C++? They are different languages. In C++ you can use [std::bitset](http://en.cppreference.com/w/cpp/utility/bitset). — Anton Savin, May 19 '15 at 07:42
What constitutes a win condition in your game? I imagine that would have a lot to do with the solution to this issue. — Roddey Frost, May 19 '15 at 07:42
@AntonSavin C++ is fine. Redings bitset notes *If the size of the bitset is not known at compile time, std::vector or boost::dynamic_bitset may be used.* — c.bear, May 19 '15 at 08:21
@RoddeyFrost k tiles in a row. I found Ammer's answer here really inspiring to try to implement a generic algorithm http://stackoverflow.com/questions/7033165/algorithm-to-check-a-connect-four-field — c.bear, May 19 '15 at 08:26

Moj · Answer 1 · 2015-05-19T09:32:59.930

I wrote this code while ago just to play around with the game concept. There is no intelligence behaviour involve. just random moves to demonstrate the game. I guess this is not important for you since you are only looking for a fast check of winning conditions. This implementation is fast since I did my best to avoid for loops and use only built-in python/numpy functions (with some tricks).

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()

let me know if you have any question

UPDATE: Explanation:

At each move, look at column, row, diagonal and secondary diagonal that goes through the current cell and find consecutive cells with the current symbol. avoid scanning the whole board.

enter image description here

extracting cells in each direction:

column:

current_col = S[:,current_col_idx]

row:

current_row = S[current_row_idx,:]

Diagonal: Find the offset of the desired diagonal from the main diagonal:

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

off-diagonal:

Reverse the rows of matrix:

S_reversed_rows = S[::-1,:]

Find the row index in the new matrix

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

enter image description here

How to deal with very big Bitboards

1 Answers1