1

I was surprised Bobby Fischer couldn't find a mate in 3 within 30 minutes in this problem by Pal Benko. This made me wonder-how many actual moves are possible with so few pieces left in only 3 moves?

[FEN "8/8/8/8/4k3/8/8/2BQKB2 w - - 0 1"]

It turns out there's a lot, which I base on an estimation assuming (very crudely) 10 possible moves per piece per move, which would result in (4*10) * (1*10) * (4*10) * (1*10) * (4*10) * (1*10) = 64,000,000. But of course this is a very very rough estimation.

How can we calculate the precise number of move combinations possible in 3 moves, whist avoiding manual calculation via estimation or decision trees, and preferably using some free and open source software/engine/equation?

3
  • How do you count transpositions? E.g do you count 1. Ke2 2. Qd2 and 1. Qd2 2. Ke2 as two or as one? Commented Jun 20, 2020 at 20:13
  • @user1583209 to be totally honest, I didn’t think about that. I guess, if possible, both would be good to know!
    – stevec
    Commented Jun 20, 2020 at 20:15
  • Python-chess is a library that can find all legal moves, make moves on the board, etc. It should be easy to write a loop to count all combinations. Commented Jun 21, 2020 at 14:35

1 Answer 1

3

Your estimate is a bit high. In particular you overestimate the number of king moves. At most a king has 8 moves (not including castling which does not apply here), however here, both the black and the white king have a lot less legal moves than your estimated 10. The white king because it is on the edge of the board and the black king because it is not allowed to run into check. A more realistic number for the possible king moves would be 4. The number of legal moves for all four white pieces here is somewhere between 30 and 40. With these estimates you should have around 1 million variations which is confirmed by the data below.

I wrote a simple (should be done with recursion), not-elegant loop in python-chess to count all the legal variations until the 3rd white move and ended up with 347 863 variations. If I go one ply further (i.e. like in your example) until the 3rd black move I get: 1 403 476 variations.

The program loops through all variations and adds the number of legal moves for the 5th ply (3rd move by white). Example program below is until the 3rd white move. Simply add a loop if you want to go until the 3rd black move.

import chess

board = chess.Board("8/8/8/8/4k3/8/8/2BQKB2 w - - 0 1")

counter = 0

for move1w in board.legal_moves:
    board.push(move1w)
    for move1b in board.legal_moves:
        board.push(move1b)
        for move2w in board.legal_moves:
            board.push(move2w)
            for move2b in board.legal_moves:
                board.push(move2b)
                counter += board.legal_moves.count()
                board.pop()
            board.pop()
        board.pop()
    board.pop()

print('The number of variations is:')
print(counter)
3
  • Unbelievably cool!! It runs quickly too. Good thinking re: black's third move being irrelevant in this puzzle. The intersection of chess / combinatorial math / programming is so fascinating.
    – stevec
    Commented Jun 21, 2020 at 16:15
  • Also ~350k is still a very large number, at least relative to what I would have guessed (perhaps < 10k)
    – stevec
    Commented Jun 21, 2020 at 17:04
  • 1
    @stevec True, and while often humans can exclude a large number of variations easily, in this position, except for queen sacrifices, there are not a whole lot of moves to be excluded at first glance. That's what makes this problem particularly difficult. Commented Jun 21, 2020 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.