Quoridor

Game logic

Game Logic code

BOARD_WIDTH = 9
BOARD_HEIGHT = 9

def init_game(game_settings):
    position1 = {
        'row': 0, 
        'column': 4
        }
    position2 = {
        'row': BOARD_HEIGHT - 1, 
        'column': 4
        }

    state = {
        'player_turn_idx': 0,
        'player_positions': [position1, position2],
        'walls': [],
        'remaining_wall_count': [10, 10]
        }
    return state

def move_up(state):
    return __move_helper(state, __can_move_up, "up")

def move_down(state):
    return __move_helper(state, __can_move_down, "down")

def move_left(state):
    return __move_helper(state, __can_move_left, "left")

def move_right(state):
    return __move_helper(state, __can_move_right, "right")

def place_horizontal_wall(state, row, column):
    new_state = __place_wall_helper(state, row, column, True)
    return new_state

def place_vertical_wall(state, row, column):
    new_state = __place_wall_helper(state, row, column, False)
    return new_state

def get_game_result(state):
    if state['player_positions'][0]['row'] == BOARD_HEIGHT - 1:
        return {
            "game_result": "Winner",
            "winner_idx": 0
        }
    if state['player_positions'][1]['row'] == 0:
        return {
            "game_result": "Winner",
            "winner_idx": 1
        }
    return {
        "game_result": "NoWinnerYet"
    }

def __place_wall_helper(state, row, column, is_horizontal):
    player_idx = state['player_turn_idx']
    if state['remaining_wall_count'][player_idx] <= 0:
        raise InvalidActionError("no more walls to place")
    if row < 0 or row >= BOARD_HEIGHT - 1 or \
    column < 0 or column >= BOARD_WIDTH - 1:
        raise InvalidActionError("can't place wall there")
    for w in state['walls']:
        if w['row'] == row and w['column'] == column and w['is_horizontal'] != is_horizontal:
            raise InvalidActionError("overlapping with another wall")
        if w['is_horizontal'] and is_horizontal and w['row'] == row:
            if abs(w['column'] - column) <= 1:
                raise InvalidActionError("overlapping with another wall")
        if not w['is_horizontal'] and not is_horizontal and w['column'] == column:
            if abs(w['row'] - row) <= 1:
                raise InvalidActionError("overlapping with another wall")

    state['walls'].append({
        'row': row, 
        'column': column, 
        'is_horizontal': is_horizontal
        })

    if not __has_path_to(state, BOARD_HEIGHT - 1, state['player_positions'][0]):
        state['walls'].pop() # Just clean up so we don't modify the state accidentally
        raise InvalidActionError("wall seals the path to the top")
    if not __has_path_to(state, 0, state['player_positions'][1]):
        state['walls'].pop() # Just clean up so we don't modify the state accidentally
        raise InvalidActionError("wall seals the path to the bottom")

    state["player_turn_idx"] = (state["player_turn_idx"] + 1) % 2
    state['remaining_wall_count'][player_idx] -= 1
    return state

def __move_helper(state, direction_func, direction_str):
    player_idx = state['player_turn_idx']
    other_player_idx = (player_idx + 1) % 2
    player_position = state['player_positions'][player_idx]
    other_player_position = state['player_positions'][other_player_idx]
    wall_set = set([(w['row'], w['column'], w['is_horizontal']) for w in state['walls']])
    
    move_coordinate = direction_func(wall_set, player_position['row'], player_position['column'])
    if not move_coordinate:
        raise InvalidActionError("cannot move " + direction_str)
    if move_coordinate == (other_player_position['row'], other_player_position['column']):
        move_more = direction_func(wall_set, move_coordinate[0], move_coordinate[1])
        if not move_more:
            raise InvalidActionError("cannot move " + direction_str + " over other player")
        state['player_positions'][player_idx]['row'] = move_more[0]
        state['player_positions'][player_idx]['column'] = move_more[1]
    else:
        state['player_positions'][player_idx]['row'] = move_coordinate[0]
        state['player_positions'][player_idx]['column'] = move_coordinate[1]
    state['player_turn_idx'] = other_player_idx
    return state

def __can_move_up(wall_set, r, c):
    if (r, c, True) not in wall_set and \
        (r, c - 1, True) not in wall_set and \
            r + 1 < BOARD_HEIGHT:
        return (r + 1, c)
    return None

def __can_move_down(wall_set, r, c):
    if (r - 1, c, True) not in wall_set and \
            (r - 1, c - 1, True) not in wall_set and \
            r - 1 >= 0:
        return (r - 1, c)
    return None

def __can_move_left(wall_set, r, c):
    if (r, c - 1, False) not in wall_set and \
            (r - 1, c - 1, False) not in wall_set and \
            c - 1 >= 0:
        return (r, c - 1)
    return None

def __can_move_right(wall_set, r, c):
    if (r, c, False) not in wall_set and \
            (r - 1, c, False) not in wall_set and \
            c + 1 < BOARD_WIDTH:
        return (r, c + 1)
    return None

def __has_path_to(state, target_row, position):
    """
    Does a dfs search from position to target. return true if there is a path
    """
    visited = set()
    stack = [(position['row'], position['column'])]
    wall_set = set([(w['row'], w['column'], w['is_horizontal']) for w in state['walls']])
    while len(stack) > 0:
        node = stack.pop()
        if node[0] == target_row:
            return True
        if node in visited:
            continue
        r, c = node
        visited.add(node)
        neighbors = [__can_move_up(wall_set, r, c), 
            __can_move_down(wall_set, r, c), 
            __can_move_right(wall_set, r, c),
            __can_move_left(wall_set, r, c)]
        for n in neighbors:
            if n:
                stack.append(n)
    return False

Game state schema

message State {
  // Required field to indicate the player who should be making the next move
  // Values = 0 or 1
  int32 player_turn_idx = 1;

  // Array of player positions, of length 2
  repeated Position player_positions = 2;

  // These are the walls that have been placed on the board.
  repeated Wall walls = 3;

  // Array of length 2, storing the number of wall pieces remaining for each player
  // that can still be placed onto the board.
  repeated int32 remaining_wall_count = 4;
}

/*
Walls have a length of 2. 
A horizontal wall in <row 0, column 0> blocks player piece at both <row 0, column 0> and <row 0, column 1> from going up.
A vertical wall in <row 0, column 0> blocks player piece at both <row 0, column 0> and <row 1, column 0> from going right.
Both horizontal and vertical walls can be placed between rows 0-7 and columns 0-7 inclusive. 
*/
message Wall {
  int32 row = 1;
  int32 column = 2;
  bool is_horizontal = 3;
}

message Position {
  int32 row = 1;
  int32 column = 2;
}

Action schema

move_up()
move_down()
move_left()
move_right()
place_horizontal_wall(int row, int column)
place_vertical_wall(int row, int column)

Start building now