1

I have to write this function that generates a game tree for Othello (or Reversi), without using any library, that at the end gives me as an output a tuple (a,b,c) with:

  • a: the number of situations that result in a black win
  • b: the number of situations that result in a white win
  • c: the number of situations that result in a draw.

I have to work with these boards given as a txt file, as such:

. . W W
. . B B
W W W B
W B B W

The problem is I get a wrong output (different from the expected one). In the given exemple above, the output tuple should be (2, 16, 0), but I get (5, 7, 11). Below I will leave you the code, and I can't figure out what did I do wrong.

def generate_game_tree(filename: str):
    
    # Load the board from the file
    board = [line.split() for line in open(filename)]

    # Initialize the game tree with the root node representing the current board state
    game_tree = [(board, 0)]
    black_count = 0
    white_count = 0
    draw_count = 0
    # Generate the game tree by expanding the nodes in a breadth-first manner
    i = 0
    while i < len(game_tree):
        node = game_tree[i]
        board, _ = node
        valid_moves = get_valid_moves(board)
        for move in valid_moves:
            new_board = make_move(board, move)
            game_tree.append((new_board, i))
        i += 1
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == "W":
                white_count += 1
            if board[i][j] == "B":
                black_count += 1
            else:
                draw_count += 1
                 
    return black_count, white_count, draw_count


def make_move(board, move):
    flips = []
    x, y = move
    curr_color = board[x][y]
    for dx, dy in [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]:
        x, y = move
        x += dx
        y += dy
        if not (0 <= x < len(board) and 0 <= y < len(board[0])):
            continue
        if board[x][y] != '.':
            continue
        while board[x][y] != curr_color:
            flips.append((x, y))
            x += dx
            y += dy
            if not (0 <= x < len(board) and 0 <= y < len(board[0])):
                break
    return flips


def get_valid_moves(board):
    valid_moves = []
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] != '.':
                continue
            flips = make_move(board, (i, j))
            if flips:
                valid_moves.append((i, j))
    return valid_moves
ggorlen
  • 44,755
  • 7
  • 76
  • 106
Jake Sparrow
  • 11
  • 1
  • 2
    When starting to debug this, I immediately bump into a multitude of distinct problems. Did you debug your code at all with a debugger, setting breakpoints, inspecting variables, ...? What were your findings? – trincot Dec 21 '22 at 20:40
  • You apply all this effort to build up the `game_tree` list, but after the while-loop you aren't actually using it for anything? – Paul M. Dec 21 '22 at 20:44
  • There are too many missing and wrong parts. There is no generation of new boards, there is no *placing* of new discs, there is no check for a full board, there is no check if a move *can* be made such that the other player should move again, the `make_move` function flips discs before checking that the series ends at a right-colored disc, `make_move` returns a list of coordinates, but you assign it as if it is a new board, there is no management of taking turns (different color), there is no check for a win, instead of counting wins, it counts disc colors, ... 99% is missing. Too broad. – trincot Dec 21 '22 at 21:46

0 Answers0