Python: Pawn race

Question

Another day, another Chess related CodeFights problem.

Pawn Race

Pawn race is a game for two people, played on an ordinary 8 × 8 chessboard. The first player has a white pawn, the second one - a black pawn. Initially the pawns are placed somewhere on the board so that the 1st and the 8th rows are not occupied. Players take turns to make a move.

White pawn moves upwards, black one moves downwards. The following moves are allowed:

• one-cell move on the same vertical in the allowed direction
• two-cell move on the same vertical in the allowed direction, if the pawn is standing on the 2nd (for the white pawn) or the 7th (for the black pawn) row. Note that even with the two-cell move a pawn can't jump over the opponent's pawn
• capture move one cell forward in the allowed direction and one cell to the left or to the right.

The purpose of the game is to reach the the 1st row (for the black pawn) or the 8th row (for the white one), or to capture the opponent's pawn.

Given the initial positions and whose turn it is, determine who will win or declare it a draw (i.e. it is impossible for any player to win). Assume that the players play optimally.

It is guaranteed that white ≠ black.

Example

• For white = "e2", black = "e7" and toMove = 'w', the output should be pawnRace(white, black, toMove) = "draw".
• For white = "e3", black = "d7" and toMove = 'b', the output should be pawnRace(white, black, toMove) = "black".
• For white = "a7", black = "h2" and toMove = 'w', the output should be pawnRace(white, black, toMove) = "white".

Code

def pawnRace(white, black, to_move):
    winner = {'w': 'white',
              'b': 'black'}

    _to_piece = lambda piece: [ord(piece[0])-ord('a'), int(piece[1])]
    white_file, white_rank = _to_piece(white)
    black_file, black_rank = _to_piece(black)

    # if on the same file and black is on a higher rank,
    # they'll bump and will not be able to pass eachother
    if(white_file == black_file and black_rank > white_rank):
        return 'draw'

    def can_capture(black_rank, black_file, white_rank, white_file):
        """return True if a piece can be captured"""
        return abs(black_file - white_file) == 1 and \
               abs(white_rank - black_rank) == 1 and \
               white_rank < black_rank

    while True:
        # if piece can capture: return winner
        if can_capture(black_rank, black_file, white_rank, white_file):
            return winner[to_move]

        # else move
        if to_move == 'w':
            if white_rank != 2 or \
               can_capture(black_rank, black_file, white_rank + 2, white_file):
                white_rank += 1
            else:
                white_rank += 2

        if to_move == 'b':
            if black_rank != 7 or \
               can_capture(black_rank - 2, black_file, white_rank, white_file):
                black_rank -= 1
            else:
                black_rank -= 2

        # if piece is on promotion square: return winner
        if white_rank == 8 or black_rank == 1:
            return winner[to_move]

        to_move = 'w' if to_move == 'b' else 'b'

Notes

This challenge is missing the en-passant move

I really tried my best this time to make it hard for all code-reviewers to critique my approach by making it readable while still keeping it simple. However as always I wonder how I did, and therefore feel the need to post it here.

Is there anything you would change or improve to my implementation?

Answer 1

This code is reasonably clear - the variables are well named and obvious, and the algorithm is reasonably transparent. There's not much in the way of low-level refactoring that I can suggest:

Make the board height a declared constant

The value 8 appears in a couple of places (disguised as 7 in one of them). This makes it hard to generalise to a different size of chessboard.

---

I do have a suggestion that might improve the algorithm:

Reduce the problem complexity

It turns out that we don't need to care about the actual file each piece is in - just the relationship between the files. Also, we only care about the number of turns, so perhaps we don't need to simulate each move. There are three possibilities:

1. Pieces are separated by at least one empty file:

   The game is a direct race; there's no impediment to the pawns both moving forward in every turn. The number of turns to win is determined by the shortest distance to cover (subtracting one, if there's a possible 2-square move).

2. Pieces are on the same file:

   If the pawns don't need to pass each other (i.e. white's rank is higher than black's rank), then it's a direct race - see above.

   Otherwise, the game is drawn.

3. Pieces are on adjacent files:

   If the pawns don't need to pass each other, then it's a direct race as before.

   Otherwise, there's an opportunity to win by capture - for the first player if the pawns start an odd distance apart, or for the second player if they start an even distance apart.

   Again, the 2-square first move adds a complication. This may give an advantage to the second player if both are able to choose one or two squares for the first move, for example.

Once you've determined whether the players need to move two squares as the first move (if allowed), then the number of turns to the end of the game is an algebraic expression (i.e. O(1) time), and it's not necessary to simulate each turn individually. This observation is likely helpful if you want to extend this to larger boards (e.g. a 1e9 x 1e9 chessboard).

Answer 2

This code seems roughly twice as long as necessary. EDIT: seems longer than necessary. (I had scrolled down and was looking at the last window full of code.)

There is a symmetry between the special case for ranks 2 and 7. Or, switching to zero-origin, between ranks 1 and 6, that is between 1 and 7 - 1.

Your API is organized in terms of White and Black. I suggest to organize it in terms of Player and Opponent. Then your function has just a single action to consider before it returns, and you make two function calls per move.

The identifier _to_piece() seems like it would be better named _to_coords(), or at least _from_piece(). Thank you for calling it a helper rather than part of the public API, that's good.

EDIT: Think of the game as having a single "player" (your function) seated at a table, and on each turn the board is spun 180° and the player is told the current color, 0/1, W/B. Now the two if to_move == 'w' clauses get buried in a make_move() helper. Choosing the player to_move = 'w' if to_move == 'b' else 'b' might be simplified to to_move = 1 - to_move if you choose to make it a numeric index. Use 'wb'[to_move] for output.

The conditional for xxxxx_rank += 1 or += 2 could be buried in a helper, so you can unconditionally increment by move_amount(). The if white_rank == 8 or black_rank == 1: could just test whether Player arrived at last rank, without worrying about Opponent. Also, can_capture() is a very nice helper, but it would become simpler once it only needed to consider Player making a forward capturing move.