Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <pre><code>import chess
  
  board = chess.Board(&quot;8/8/8/8/4k3/8/8/2BQKB2 w - - 0 1&quot;)
  
  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)
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-21T16:15:22.473Z
Answers.Text: 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.
Answers.UserDisplayName: stevec
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-21T17:04:22.323Z
Answers.Text: Also ~350k is still a very large number, at least relative to what I would have guessed (perhaps < 10k)
Answers.UserDisplayName: stevec
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-21T17:51:30.853Z
Answers.Text: @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.
Answers.UserDisplayName: user1583209
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-21T16:05:20.793Z
Answers.LastActivityDate: 2020-06-21T16:20:58.840Z
Answers.LastEditDate: 2020-06-21T16:20:58.840Z
Answers.UserDisplayName: user1583209
Body: <p>I was surprised Bobby Fischer couldn't find a mate in 3 within 30 minutes in this <a href="https://www.youtube.com/watch?v=tvMftUQJl5Q" rel="nofollow noreferrer">problem by Pal Benko</a>. This made me wonder-how many actual moves are possible with so few pieces left in only 3 moves?</p>
  <pre><code>[FEN &quot;8/8/8/8/4k3/8/8/2BQKB2 w - - 0 1&quot;]
  </code></pre>
  <p>It turns out there's a lot, which I base on an estimation assuming (<em>very</em> crudely) 10 possible moves per piece per move, which would result in <code>(4*10) * (1*10) * (4*10) * (1*10) * (4*10) * (1*10)</code> = 64,000,000. But of course this is a very very rough estimation.</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-20T20:13:29.000Z
Comments.Text: How do you count transpositions? E.g do you count 1. Ke2 2. Qd2 and 1. Qd2  2. Ke2 as two or as one?
Comments.UserDisplayName: user1583209
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-20T20:15:28.463Z
Comments.Text: @user1583209 to be totally honest, I didn’t think about that. I guess, if possible, both would be good to know!
Comments.UserDisplayName: stevec
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-21T14:35:35.657Z
Comments.Text: 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.
Comments.UserDisplayName: user1583209
Tags: <engines><software><problems><mathematics>
Title: Calculating the precise number of combinations of possible moves from a given position
ThreadText: # Calculating the precise number of combinations of possible moves from a given position
  
  (Asked by: username_0 on 2020-06-20)
  
  I was surprised Bobby Fischer couldn't find a mate in 3 within 30 minutes in this [problem by Pal Benko](https://www.youtube.com/watch?v=tvMftUQJl5Q). 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?
  
  **Tags:** engines, software, problems, mathematics
  
  > **Comments:**
  > **username_1**: How do you count transpositions? E.g do you count 1. Ke2 2. Qd2 and 1. Qd2  2. Ke2 as two or as one?  
  > **username_0**: @username_1 to be totally honest, I didn’t think about that. I guess, if possible, both would be good to know!  
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-21. Score: 3 | Accepted answer
  
  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)
  
  ```
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: Also ~350k is still a very large number, at least relative to what I would have guessed (perhaps < 10k)  
  > **username_1**: @username_0 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.  
  
  ---
  
  