Writing a chess game in python [Day 4]

We're still in lockdown due to COVID-19, and I'm using the time to implement a textual chess game with my 12yo. In this series I'll be sharing what we did and how the project evolved.

---

We left off in Day 3 with a valid move checks test suite for common scenarios (target square out of bounds or occupied by a piece with the same color) and rook moves.

Today we decided to implement moving a rook on the board.

We defined this interface:

def move(board, piece, target_rank, target_file):
  pass

When we considered what we would need in order to implement it, we realized that checking if a move was valid wouldn't be enough, we'd have to know where the valid piece was located. And since the is_valid_move calculates that location as part of the validation checks - it made much more sense to combine the two instead of implementing a second method in addition to the validation method.

To be honest, I knew that's what we would end up doing, but I let him figure that part out on his own, it's part of the learning process. The additional advantage is it showed him the value of having tests - after we changed the method to return something else, we made a few small changes to the existing tests and when they passed we could be pretty confident we didn't cause any regression in the functionality.

Here's what we changed:

def find_valid_move(board, piece, target_rank, target_file):
  # out of bounds
  if  target_rank < 0 or target_rank > 7:
    return -1, -1
  if  target_file < 0 or target_file > 7:
    return -1, -1
  # piece with same color is in the target square
  if board[target_rank][target_file][0] == piece[0]:
    return -1, -1

  if piece in ("WR", "BR"):
    return find_valid_rook_move(board, piece, target_rank, target_file)

  return -1, -1

def find_valid_rook_move(board, piece, target_rank, target_file):
  found_rank = -1
  found_file = -1
  for i in range(8):
    if board[target_rank][i] == piece:
      found_rank = target_rank
      found_file = i
      break

  if found_rank == -1:
    for i in range(8):
      if board[i][target_file] == piece:
        found_rank = i
        found_file = target_file
        break

  if found_rank < 0 or found_file < 0:
    return -1, -1 

  if found_rank == target_rank:
    start_file = min(target_file+1, found_file+1)
    end_file = max(target_file, found_file)
    for i in range(start_file, end_file):
        if board[target_rank][i] != EMPTY:
          return -1, -1
  else: # found_file == target_file
    start_rank = min(target_rank+1, found_rank+1)
    end_rank = max(target_rank, found_rank)
    for i in range(start_rank, end_rank):
        if board[i][target_file] != EMPTY:
          return -1, -1
  return found_rank, found_file

This is the exact same logic only we return (-1, -1) when no valid piece is found, and (found_rank, found_file) if we found a valid piece.

Next we implemented the move logic as follows:

def move(board, piece, target_rank, target_file):
  found_rank, found_file = find_valid_move(board, piece, 
  target_rank, target_file)
  if (found_rank, found_file) != (-1, -1):
    board[target_rank][target_file] = piece
    board[found_rank][found_file] = EMPTY
    return True
  return False

Next we did a small manual test to see that move worked as expected:

board = create_board()
board[1][0] = EMPTY
result = move(board, "WR", 5, 0)
print_board(board)

And the surprising output was:

   ---- ---- ---- ---- ---- ---- ---- ----
8 | BR | BN | BB | BQ | BK | BB | BN | BR |
   ---- ---- ---- ---- ---- ---- ---- ----
7 | BP | BP | BP | BP | BP | BP | BP | BP |
   ---- ---- ---- ---- ---- ---- ---- ----
6 | WR |    |    |    |    |    |    |    |
   ---- ---- ---- ---- ---- ---- ---- ----
5 | WR |    |    |    |    |    |    |    |
   ---- ---- ---- ---- ---- ---- ---- ----
4 | WR |    |    |    |    |    |    |    |
   ---- ---- ---- ---- ---- ---- ---- ----
3 | WR |    |    |    |    |    |    |    |
   ---- ---- ---- ---- ---- ---- ---- ----
2 |    | WP | WP | WP | WP | WP | WP | WP |
   ---- ---- ---- ---- ---- ---- ---- ----
1 |    | WN | WB | WQ | WK | WB | WN | WR |
   ---- ---- ---- ---- ---- ---- ---- ----
    a    b    c    d    e    f    g    h  

There was no way 12yo would figure this one out, but I realized what had happened right away and I should have known better. Oops. I had initialized the board using:

board = [[EMPTY]*8]*8

Which creates a single list and duplicates it 8 times. When we changed something in rank 5 it changed it in all the middle rows (the other rows were replaced with rows which contained the pieces). Very wrong. Don't do this.

12yo had some trouble understanding what went wrong and why, so I created this simple example to explain:

sub_list = [1,2,3]
test_list = [sub_list]*3
print(test_list)
sub_list[0] = 5
print(test_list)

And he kind of went "oooohhhh, yeah... that will change the item in all the lists at once" so I figured he understood.
Output:

[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[5, 2, 3], [5, 2, 3], [5, 2, 3]]

Once we fixed that, it worked correctly.
12yo wrote the following test:

def test_move_rook():
  board = create_board()
  board[1][0] = EMPTY
  result = move(board, "WR", 5, 0)
  assert result
  print("test_move_rook passed")

Not bad! However, I asked him if this would have found the problem we saw when we ran the test manually. He thought about it a bit and said "no". I added the expected_board bit to the test:

def test_move_rook():
  board = create_board()
  board[1][0] = EMPTY

  expected_board = create_board()
  expected_board[1][0] = EMPTY
  expected_board[0][0] = EMPTY
  expected_board[5][0] = "WR"

  result = move(board, "WR", 5, 0)
  assert result
  assert board == expected_board
  print("test_move_rook passed")

I knew this was coming but I didn't want to add it into the mix too soon... Now was the time however: What happens if there are two valid pieces? 12yo was starting to regret he didn't accept my original idea of specifying ahead of time where we were moving the piece from as well as the target instead of calculating possible locations, but I wasn't going to give up now.

He said that when there are two matching pieces the players specify the rank or file of the piece, but to make things just a tiny bit simpler I suggested we specify the rank and file. As he'd seen my advice is usually sound, he decided to accept this idea.

We changed the find_valid_rook_move method as follows:

1. We added source_rank and source_file to enable specifying which item we wanted to move.
2. Instead of stopping once we found a matching piece, we added it to a list of found_pieces
3. If no pieces were found, return -1, -1
4. If we found more than one piece, try to find one that matches the given source_rank and source_file.
5. If there's only a single matching piece, use it.
6. Then continue and check if there's no other piece blocking it.

def find_valid_rook_move(board, piece, target_rank, target_file, source_rank=-1, source_file=-1):
  found_pieces = []
  for i in range(8):
    if board[target_rank][i] == piece:
      found_rank = target_rank
      found_file = i
      found_pieces.append((found_rank, found_file))

  for i in range(8):
    if board[i][target_file] == piece:
      found_rank = i
      found_file = target_file
      found_pieces.append((found_rank, found_file))

  if len(found_pieces) == 0:
    return -1, -1 

  # don't know which item to choose
  found_rank = -1
  found_file = -1
  if (len(found_pieces) > 1):
    if source_rank < 0 or source_file < 0:
      return -1, -1
    for rank, file in found_pieces:
      if rank == source_rank and file == source_file:
        found_rank = rank
        found_file = file
  else:
    found_rank, found_file = found_pieces[0]

  if (found_rank, found_file) == (-1, -1):
    return -1, -1 

  if found_rank == target_rank:
    start_file = min(target_file+1, found_file+1)
    end_file = max(target_file, found_file)
    for i in range(start_file, end_file):
        if board[target_rank][i] != EMPTY:
          return -1, -1
  else: # found_file == target_file
    start_rank = min(target_rank+1, found_rank+1)
    end_rank = max(target_rank, found_rank)
    for i in range(start_rank, end_rank):
        if board[i][target_file] != EMPTY:
          return -1, -1
  return found_rank, found_file

And added a test:

def test_double_move_rook():
  board = create_board()
  board[1][0] = EMPTY
  board[0][7] = EMPTY
  board[5][0] = "WR"
  result = move(board, "WR", 3, 0)
  assert not result

  expected_board = create_board()
  expected_board[1][0] = EMPTY
  expected_board[0][7] = EMPTY
  expected_board[5][0] = "WR"
  expected_board[3][0] = "WR"
  expected_board[0][0] = EMPTY
  result = move(board, "WR", 3, 0, 0, 0)
  assert result
  assert board == expected_board

  print("test_double_move_rook passed")

There's one more scenario we should check though, and I already know it won't pass... What happens if there are two matching pieces on the board but one of them is blocked? I let 12yo write the test and then try to figure out why it failed.

  ...
  board = create_board()
  board[0][7] = EMPTY
  board[5][0] = "WR"
  expected_board = create_board()
  expected_board[0][7] = EMPTY
  expected_board[3][0] = "WR"
  expected_board[0][0] = "WR"
  result = move(board, "WR", 3, 0)
  assert result
  assert board == expected_board

We added print commands in various places in find_valid_rook_move and what we found was that since we check validity after choosing a piece, we were coming to the conclusion we didn't have enough information (i.e. source_rank and source_file too early).

We switched around the logic to find valid_pieces before verifying we need source_rank and source_file, and it worked (12yo made these changes after I walked him through the logic 👏):

def find_valid_rook_move(board, piece, target_rank, target_file, source_rank=-1, source_file=-1):
  found_pieces = []
  for i in range(8):
    if board[target_rank][i] == piece:
      found_rank = target_rank
      found_file = i
      found_pieces.append((found_rank, found_file))

  for i in range(8):
    if board[i][target_file] == piece:
      found_rank = i
      found_file = target_file
      found_pieces.append((found_rank, found_file))

  if len(found_pieces) == 0:
    return -1, -1 

  valid_pieces = []

  for found_rank, found_file in found_pieces:
    is_valid = True
    if found_rank == target_rank:
      start_file = min(target_file+1, found_file+1)
      end_file = max(target_file, found_file)
      for i in range(start_file, end_file):
          if board[target_rank][i] != EMPTY:
            is_valid = False
            break
    else: # found_file == target_file
      start_rank = min(target_rank+1, found_rank+1)
      end_rank = max(target_rank, found_rank)
      for i in range(start_rank, end_rank):
          if board[i][target_file] != EMPTY:
            is_valid = False
            break
    if is_valid:
      valid_pieces.append((found_rank, found_file))

  # don't know which item to choose
  found_rank = -1
  found_file = -1
  if len(valid_pieces) > 1:
    if source_rank < 0 or source_file < 0:
      return -1, -1
    for rank, file in valid_pieces:
      if rank == source_rank and file == source_file:
        found_rank = rank
        found_file = file
  elif len(valid_pieces) == 1:
    found_rank, found_file = valid_pieces[0]

  return found_rank, found_file

Now we're all setup with a template for implementing moving all the other pieces, so I hope we can get through the next ones a bit faster.

Join us next time!

---

Final code for today (including modified tests):

EMPTY = "  "

def print_board(board):
  row_number = 8
  print("  ", end="")
  print(" ----"*8)
  for row in reversed(board):
      print(row_number, end=" ")
      row_number -= 1
      for cell in row:
          print("| {} ".format(cell), end="")
      print("|")
      print("  ", end="")
      print(" ----"*8)
  print("  ", end="")
  for letter in ['a','b','c','d','e','f','g','h']:
      print("  {}  ".format(letter), end="")
  print("")

def create_board():
  board = []

  board.append(["WR","WN","WB","WQ","WK","WB","WN","WR"])
  board.append(["WP","WP","WP","WP","WP","WP","WP","WP"])
  for i in range(2, 6):
    board.append([EMPTY]*8)
  board.append(["BP","BP","BP","BP","BP","BP","BP","BP"])
  board.append(["BR","BN","BB","BQ","BK","BB","BN","BR"])

  return board

def find_valid_move(board, piece, target_rank, target_file, source_rank=-1, source_file=-1):
  # out of bounds
  if  target_rank < 0 or target_rank > 7:
    return -1, -1
  if  target_file < 0 or target_file > 7:
    return -1, -1
  # piece with same color is in the target cell
  if board[target_rank][target_file][0] == piece[0]:
    return -1, -1

  if piece in ("WR", "BR"):
    return find_valid_rook_move(board, piece, target_rank, target_file, source_rank, source_file)

  return -1, -1

def find_valid_rook_move(board, piece, target_rank, target_file, source_rank=-1, source_file=-1):
  found_pieces = []
  for i in range(8):
    if board[target_rank][i] == piece:
      found_rank = target_rank
      found_file = i
      found_pieces.append((found_rank, found_file))

  for i in range(8):
    if board[i][target_file] == piece:
      found_rank = i
      found_file = target_file
      found_pieces.append((found_rank, found_file))

  if len(found_pieces) == 0:
    return -1, -1 

  valid_pieces = []

  for found_rank, found_file in found_pieces:
    is_valid = True
    if found_rank == target_rank:
      start_file = min(target_file+1, found_file+1)
      end_file = max(target_file, found_file)
      for i in range(start_file, end_file):
          if board[target_rank][i] != EMPTY:
            is_valid = False
            break
    else: # found_file == target_file
      start_rank = min(target_rank+1, found_rank+1)
      end_rank = max(target_rank, found_rank)
      for i in range(start_rank, end_rank):
          if board[i][target_file] != EMPTY:
            is_valid = False
            break
    if is_valid:
      valid_pieces.append((found_rank, found_file))

  # don't know which item to choose
  found_rank = -1
  found_file = -1
  if len(valid_pieces) > 1:
    if source_rank < 0 or source_file < 0:
      return -1, -1
    for rank, file in valid_pieces:
      if rank == source_rank and file == source_file:
        found_rank = rank
        found_file = file
  elif len(valid_pieces) == 1:
    found_rank, found_file = valid_pieces[0]

  return found_rank, found_file


def move(board, piece, target_rank, target_file, source_rank=-1, source_file=-1):
  found_rank, found_file = find_valid_move(board, piece, 
  target_rank, target_file, source_rank, source_file)
  if (found_rank, found_file) != (-1, -1):
    board[target_rank][target_file] = piece
    board[found_rank][found_file] = EMPTY
    return True
  return False

# ----------------------- tests -------------------

def test_move_rook():
  board = create_board()
  board[1][0] = EMPTY

  expected_board = create_board()
  expected_board[1][0] = EMPTY
  expected_board[0][0] = EMPTY
  expected_board[5][0] = "WR"

  result = move(board, "WR", 5, 0)
  assert result
  assert board == expected_board
  print("test_move_rook passed")

def test_double_move_rook():
  board = create_board()
  board[1][0] = EMPTY
  board[0][7] = EMPTY
  board[5][0] = "WR"
  result = move(board, "WR", 3, 0)
  assert not result

  expected_board = create_board()
  expected_board[1][0] = EMPTY
  expected_board[0][7] = EMPTY
  expected_board[5][0] = "WR"
  expected_board[3][0] = "WR"
  expected_board[0][0] = EMPTY
  result = move(board, "WR", 3, 0, 0, 0)
  assert result
  assert board == expected_board

  board = create_board()
  board[0][7] = EMPTY
  board[5][0] = "WR"
  expected_board = create_board()
  expected_board[0][7] = EMPTY
  expected_board[3][0] = "WR"
  expected_board[0][0] = "WR"
  result = move(board, "WR", 3, 0)
  assert result
  assert board == expected_board
  print("test_double_move_rook passed")

def test_is_rank_valid():
  board = create_board()
  result = find_valid_move(board, "xx", 22, 4)
  assert result == (-1, -1)
  result = find_valid_move(board, "xx", -2020, 4)
  assert result == (-1, -1)
  print("test_is_rank_valid passed")

def test_is_file_valid():
  board = create_board()
  result = find_valid_move(board, "xx", 0, 22)
  assert result == (-1, -1)
  result = find_valid_move(board, "xx", 0, -2020)
  assert result == (-1, -1)
  print("test_is_file_valid passed")

def test_is_target_square_taken():
  board = create_board()
  result = find_valid_move(board, "Wx", 0, 1)
  assert result == (-1, -1)
  print("test_is_target_square_taken passed")

def test_rook_is_blocked():
  board = create_board()
  result = find_valid_rook_move(board, "BR", 5, 0)
  assert result == (-1, -1)
  board[7][5] = EMPTY
  result = find_valid_rook_move(board, "BR", 7, 5)
  assert result == (-1, -1)
  print("test_rook_is_blocked passed")

def test_rook_is_not_blocked():
  board = create_board()
  board[1][0] = EMPTY
  result = find_valid_rook_move(board, "WR", 2, 0)
  assert result == (0,0)
  board[0][1] = EMPTY
  result = find_valid_rook_move(board, "WR", 0, 1)
  assert result == (0,0)
  print("test_rook_is_not_blocked passed")

def run_tests():
  test_is_rank_valid()
  test_is_file_valid()
  test_is_target_square_taken()
  test_rook_is_blocked()
  test_rook_is_not_blocked()
  test_move_rook()
  test_double_move_rook()
run_tests()