Answers.Body: <p>There are many ways to generate positions for perft tests. This approach uses the positions in the pgn file. In this example I use the candidates 2022 games.</p>
  <p>You can use other pgn files to generate positions.</p>
  <h3>Code</h3>
  <p>python script using python-chess library.</p>
  <pre><code>&quot;&quot;&quot;Generate positions from candidates 2022 positions.
  
  Python:
    version &gt;= 3.7
  
  requirements:
    pip install chess
  &quot;&quot;&quot;
  
  
  import chess.pgn
  
  
  def genpos(pgnfile):
      &quot;&quot;&quot;Save positions from pgnfile.
  
      Read each position in each game in pgnfile and for each position,
      generate all legal moves and save the resulting positions in epd format.
      Also save the current position.
  
      Sample output:
        rnb1kbnr/pp2pppp/1q1p4/8/3NP3/8/PPP2PPP/RNBQKB1R w KQkq -,42
  
      The 42 is the number of legal moves.
      &quot;&quot;&quot;
      tmp = {}  # {&lt;epd1,legalmoves&gt;: 1, &lt;epd2,legalmoves&gt;: 1, ...}
      
      with open(pgnfile, 'r') as f:
          while True:
              game = chess.pgn.read_game(f)
              if game is None:
                  break
  
              for node in game.mainline():
                  board = node.parent.board()
                  epd = board.epd()
                  print(epd)  # console log
  
                  # Copy the current board and generate all moves, get
                  # the epd and save it.
                  tboard = board.copy()
                  for m in tboard.legal_moves:
                      # Push the move and save the resulting position.
                      tboard.push(m)
                      tepd = tboard.epd()
  
                      # Save unique positions only.
                      legal_moves = tboard.legal_moves.count()
                      key = f'{tepd},{legal_moves}'
                      if key not in tmp:
                          tmp[key] = 1
                      tboard.pop()  # unmake and continue
  
                  # Also save the current position.
                  legal_moves = board.legal_moves.count()
                  key = f'{epd},{legal_moves}'
                  if key not in tmp:
                      tmp[key] = 1
                      
      # Save positions in a file.
      with open('candidates.epd', 'w') as w:
          for epd in list(tmp.keys()):
              w.write(f'{epd}\n')
  
  
  # Start
  pgnfile = 'wchcand22.pgn'
  # download: https://theweekinchess.com/assets/files/pgn/wchcand22.pgn
  genpos(pgnfile)
  </code></pre>
  <h3>Output</h3>
  <pre><code>1r4r1/5p1k/p2p1qQp/2b1nPp1/p7/6RP/B1R2PPK/2B5 b - -,5
  1r4r1/5p1k/p2p1q1p/2b1nPQ1/p7/6RP/B1R2PPK/2B5 b - -,48
  1r4r1/5p1k/p2p1q1p/2b1nPp1/p6Q/6RP/B1R2PPK/2B5 b - -,48
  1r4r1/5p1k/p2p1q1p/2b1nPp1/p5Q1/6RP/B1R2PPK/2B5 b - -,46
  1r4r1/5p1k/p2p1q1p/2b1nPp1/p7/5QRP/B1R2PPK/2B5 b - -,47
  </code></pre>
  <p>The 5, 48 ... are the legal moves from the given positions.
  Test your engine with those legal moves.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-06T04:35:35.450Z
Answers.LastActivityDate: 2022-07-06T04:35:35.450Z
Answers.UserDisplayName: ferdy
Answers.Body: <p>There's no approach which can give you the distribution you want better than brute force enumeration.  The problem is, at the very least, at least as difficult as identifying the number of possible positions after N moves, which is non-trivial.</p>
  <p>If you had an oracle which generated positions, and you wanted to validate that it is actually a uniform distribution, it would be at least as difficult as looking at a given position and determining if it is reachable in N moves.</p>
  <p>Once N gets big enough, you may be able to solve this.  At some point the number of legal positions that cannot be reached shrinks.  We could compute N by looking at how many moves it takes to construct a pawn structure plus the number of moves to get every piece to any location on the board.</p>
  <p>For small N, you can brute force.  For large N, you can assume all legal positions are reachable.  In the middle is troublesome indeed.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-01T21:35:03.457Z
Answers.Text: Why the fuzz about N? A position is either legal or not, no? OP seems to not care about N and rightly so I'd say, since we can loose even amounts of moves with knights and triangulate after every first move other than a3 and h3 for an odd number of moves. The oracle will thus provide uniformity by itself for all positions that are beyond a3+h3, no?
Answers.UserDisplayName: Peter Fischer
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-07T13:51:34.837Z
Answers.Text: @PeterFischer "all the fuss about N" because if do you actually want a _uniform_  distribution over _every_ possible position, you have to enumerate them all! No one has time for that...
Answers.UserDisplayName: AakashM
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-07T15:12:43.603Z
Answers.Text: @PeterFischer I think I read the wording differently.  When the OP wrote "reached from the starting position  in some amount of moves," I translated "some amount" as a chosen number, rather than an arbitrary number.
Answers.UserDisplayName: Cort Ammon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-01T20:33:32.307Z
Answers.LastActivityDate: 2022-07-01T20:33:32.307Z
Answers.UserDisplayName: Cort Ammon
Body: <p>I want to generate a random legal standard chess position. By legal I mean a chess position that can be reached from the starting position in some amount of moves. My problem is that I want this generation to be uniformly distributed over all legal chess positions. This is of course theoretically possible to achieve, simply make an array of all legal chess positions and then generate an integer between 0 and that length of the array. I was wondering however if there is a way to do this and finish in a &quot;reasonable&quot; amount of time on a modern cpu.</p>
  <p>I realize that I maybe have to change the definition of legal chess position to achieve this. If I instead choose rules like</p>
  <ul>
  <li>Exactly one king on both sides.</li>
  <li>No king can be captured on the next move.</li>
  <li>No more than 16 pieces on either side.</li>
  <li>No more than 9 pieces of any particular piece. (No more than 8 pawns.)</li>
  <li>No pawns on rank 1 and 8.</li>
  </ul>
  <p>etc. This will be approximately all legal chess positions but I'm sure there are exceptions. Is it however even possible to generate uniformly distributed positions obeying a set of rules like the above?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-01T19:27:49.033Z
Comments.Text: Promotion of pawns comes with implications: a) either opposite side has lost or moved a pawn, b) if the non-capturing promoted piece is a bishop (say a8=B), it can only move back into the board if another opponents pawn was moved; promoted rooks by capturing (cxb8=R) similarly need an additional pawn move to return (b7 pawn here); c) opposite side must have lost one of their men for every pawn changing files. Add these and you're good to go.
Comments.UserDisplayName: Peter Fischer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-01T19:31:41.880Z
Comments.Text: On how: I'd go with creating FEN strings. Their 64 or 8x8-bit format looks ideal, and imposing certain rules is then a matter of arraying the variables (trivial: numbers (=empty squares) adding up to at least 32; K and k (=kings) only once, pawn missing per every promoted piece, no pawns on first or eight rank (=8-bit substring); less trivial: kings not touching, promotion implications; hard: no king in check.  Still, looks to me like the way to go.
Comments.UserDisplayName: Peter Fischer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-01T19:58:15.940Z
Comments.Text: I'd think carefully about what you mean by "uniformly distributed."  If you mean "Given the set of all positions N moves into the game, each one has equal probability," this must necessarily involve enumerating all positions.  If you mean "each move is selected uniformly from the available moves," you get a different distribution which is much easier to compute.  If you place the pieces on the board in a uniform random distribution and exclude illegal positions, that's a different definition.
Comments.UserDisplayName: Cort Ammon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-01T19:58:41.430Z
Comments.Text: I've been burned many times by thinking "uniform distribution" meant something until I went to acutally act on it, and then realized it was more nuanced than I'd thought at first.
Comments.UserDisplayName: Cort Ammon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-01T20:20:28.130Z
Comments.Text: @CortAmmon What I mean with uniform is, given the set of all possible chess positions, after any N moves, each one has equal probability.
Comments.UserDisplayName: spinosarus123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-01T22:23:34.160Z
Comments.Text: This seems pretty easy to do. I assume the distribution stipulation means, "of all the possible moves, choose one randomly".  Chess programs do this already, except they have an algorithm to select the best move, not a random move.
  
  Is there a specific problem you want help with?  Do you program?
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-02T08:21:24.623Z
Comments.Text: @TonyEnnis I’m writing a chess engine in c. My question is not regarding choosing moves, it’s about choosing positions.
Comments.UserDisplayName: spinosarus123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-02T12:42:44.083Z
Comments.Text: Interesting. Normally a chess engine creates a new position by making a move on a board currently under evaluation. What are you trying to accomplish by selecting positions seemingly randomly.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-03T15:28:51.513Z
Comments.Text: @TonyEnnis I want to be able to generate seemingly random positions to do perft bench marks for a lot of different positions very fast.
Comments.UserDisplayName: spinosarus123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-04T04:58:55.743Z
Comments.Text: This seems straightforward, but perhaps I don't understand. It's a recursive function where all legal moves are calculated, then one is chosen randomly, rinse-repeat to desired ply. Should take a millisecond or three to generate a position.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-04T07:02:07.333Z
Comments.Text: Hmmm, I guess I could randomly generate a depth and then randomly generate moves until I’m at the desired depth. Thank you @TonyEnnis.
Comments.UserDisplayName: spinosarus123
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-06T11:16:19.453Z
Comments.Text: It makes no sense to use random legal positions in your test suite. The vast majority of these are positions that couldn't possibly happen in a real-life competitive game, so you learn nothing useful from them. Better to use a random selection of positions from real chess games -- there are plenty to choose from!
Comments.UserDisplayName: TonyK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-07T15:19:18.550Z
Comments.Text: If you're just using the randomness for performance testing, can you relax the conditions?  Is there a requirement for uniformity?  The best answer would probably be to go with TonyK's comment, testing real life situations your algorithm might actually one day have to evaluate, and ferdy's answer showing how to do it.  Then, if you want more coverage for "fuzz" testing, generate a distribution of real-looking positions (using a formula as you describe), and don't worry about whether it's actually possible.  You're looking for performance, not correctness.
Comments.UserDisplayName: Cort Ammon
Tags: <engines><programming>
Title: Uniformly generate random chess positions
ThreadText: # Uniformly generate random chess positions
  
  (Asked by: username_0 on 2022-07-01)
  
  I want to generate a random legal standard chess position. By legal I mean a chess position that can be reached from the starting position in some amount of moves. My problem is that I want this generation to be uniformly distributed over all legal chess positions. This is of course theoretically possible to achieve, simply make an array of all legal chess positions and then generate an integer between 0 and that length of the array. I was wondering however if there is a way to do this and finish in a "reasonable" amount of time on a modern cpu.
  
  I realize that I maybe have to change the definition of legal chess position to achieve this. If I instead choose rules like
  
  * Exactly one king on both sides.
  * No king can be captured on the next move.
  * No more than 16 pieces on either side.
  * No more than 9 pieces of any particular piece. (No more than 8 pawns.)
  * No pawns on rank 1 and 8.
  
  etc. This will be approximately all legal chess positions but I'm sure there are exceptions. Is it however even possible to generate uniformly distributed positions obeying a set of rules like the above?
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: Promotion of pawns comes with implications: a) either opposite side has lost or moved a pawn, b) if the non-capturing promoted piece is a bishop (say a8=B), it can only move back into the board if another opponents pawn was moved; promoted rooks by capturing (cxb8=R) similarly need an additional pawn move to return (b7 pawn here); c) opposite side must have lost one of their men for every pawn changing files. Add these and you're good to go.  
  > **username_1**: On how: I'd go with creating FEN strings. Their 64 or 8x8-bit format looks ideal, and imposing certain rules is then a matter of arraying the variables (trivial: numbers (=empty squares) adding up to at least 32; K and k (=kings) only once, pawn missing per every promoted piece, no pawns on first or eight rank (=8-bit substring); less trivial: kings not touching, promotion implications; hard: no king in check.  Still, looks to me like the way to go.  
  > **username_2**: I'd think carefully about what you mean by "uniformly distributed."  If you mean "Given the set of all positions N moves into the game, each one has equal probability," this must necessarily involve enumerating all positions.  If you mean "each move is selected uniformly from the available moves," you get a different distribution which is much easier to compute.  If you place the pieces on the board in a uniform random distribution and exclude illegal positions, that's a different definition.  
  > **username_2**: I've been burned many times by thinking "uniform distribution" meant something until I went to acutally act on it, and then realized it was more nuanced than I'd thought at first.  
  > **username_0**: @username_2 What I mean with uniform is, given the set of all possible chess positions, after any N moves, each one has equal probability.  
  > **username_3**: This seems pretty easy to do. I assume the distribution stipulation means, "of all the possible moves, choose one randomly".  Chess programs do this already, except they have an algorithm to select the best move, not a random move.  Is there a specific problem you want help with?  Do you program?  
  > **username_0**: @username_3 I’m writing a chess engine in c. My question is not regarding choosing moves, it’s about choosing positions.  
  > **username_3**: Interesting. Normally a chess engine creates a new position by making a move on a board currently under evaluation. What are you trying to accomplish by selecting positions seemingly randomly.  
  > **username_0**: @username_3 I want to be able to generate seemingly random positions to do perft bench marks for a lot of different positions very fast.  
  > **username_3**: This seems straightforward, but perhaps I don't understand. It's a recursive function where all legal moves are calculated, then one is chosen randomly, rinse-repeat to desired ply. Should take a millisecond or three to generate a position.  
  > **username_0**: Hmmm, I guess I could randomly generate a depth and then randomly generate moves until I’m at the desired depth. Thank you @username_3.  
  > **username_4**: It makes no sense to use random legal positions in your test suite. The vast majority of these are positions that couldn't possibly happen in a real-life competitive game, so you learn nothing useful from them. Better to use a random selection of positions from real chess games -- there are plenty to choose from!  
  > **username_2**: If you're just using the randomness for performance testing, can you relax the conditions?  Is there a requirement for uniformity?  The best answer would probably be to go with username_4's comment, testing real life situations your algorithm might actually one day have to evaluate, and username_5's answer showing how to do it.  Then, if you want more coverage for "fuzz" testing, generate a distribution of real-looking positions (using a formula as you describe), and don't worry about whether it's actually possible.  You're looking for performance, not correctness.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-07-01. Score: 4 | Accepted answer
  
  There's no approach which can give you the distribution you want better than brute force enumeration. The problem is, at the very least, at least as difficult as identifying the number of possible positions after N moves, which is non-trivial.
  
  If you had an oracle which generated positions, and you wanted to validate that it is actually a uniform distribution, it would be at least as difficult as looking at a given position and determining if it is reachable in N moves.
  
  Once N gets big enough, you may be able to solve this. At some point the number of legal positions that cannot be reached shrinks. We could compute N by looking at how many moves it takes to construct a pawn structure plus the number of moves to get every piece to any location on the board.
  
  For small N, you can brute force. For large N, you can assume all legal positions are reachable. In the middle is troublesome indeed.
  
  > **Comments:**
  > **username_1**: Why the fuzz about N? A position is either legal or not, no? OP seems to not care about N and rightly so I'd say, since we can loose even amounts of moves with knights and triangulate after every first move other than a3 and h3 for an odd number of moves. The oracle will thus provide uniformity by itself for all positions that are beyond a3+h3, no?  
  > **username_6**: @username_1 "all the fuss about N" because if do you actually want a _uniform_  distribution over _every_ possible position, you have to enumerate them all! No one has time for that...  
  > **username_2**: @username_1 I think I read the wording differently.  When the OP wrote "reached from the starting position  in some amount of moves," I translated "some amount" as a chosen number, rather than an arbitrary number.  
  
  ---
  
  ### Answer by username_5 on 2022-07-06. Score: 2
  
  There are many ways to generate positions for perft tests. This approach uses the positions in the pgn file. In this example I use the candidates 2022 games.
  
  You can use other pgn files to generate positions.
  
  ### Code
  
  python script using python-chess library.
  
  ```
  """Generate positions from candidates 2022 positions.
  
  Python:
    version >= 3.7
  
  requirements:
    pip install chess
  """
  
  import chess.pgn
  
  def genpos(pgnfile):
      """Save positions from pgnfile.
  
      Read each position in each game in pgnfile and for each position,
      generate all legal moves and save the resulting positions in epd format.
      Also save the current position.
  
      Sample output:
        rnb1kbnr/pp2pppp/1q1p4/8/3NP3/8/PPP2PPP/RNBQKB1R w KQkq -,42
  
      The 42 is the number of legal moves.
      """
      tmp = {}  # {<epd1,legalmoves>: 1, <epd2,legalmoves>: 1, ...}
      
      with open(pgnfile, 'r') as f:
          while True:
              game = chess.pgn.read_game(f)
              if game is None:
                  break
  
              for node in game.mainline():
                  board = node.parent.board()
                  epd = board.epd()
                  print(epd)  # console log
  
                  # Copy the current board and generate all moves, get
                  # the epd and save it.
                  tboard = board.copy()
                  for m in tboard.legal_moves:
                      # Push the move and save the resulting position.
                      tboard.push(m)
                      tepd = tboard.epd()
  
                      # Save unique positions only.
                      legal_moves = tboard.legal_moves.count()
                      key = f'{tepd},{legal_moves}'
                      if key not in tmp:
                          tmp[key] = 1
                      tboard.pop()  # unmake and continue
  
                  # Also save the current position.
                  legal_moves = board.legal_moves.count()
                  key = f'{epd},{legal_moves}'
                  if key not in tmp:
                      tmp[key] = 1
                      
      # Save positions in a file.
      with open('candidates.epd', 'w') as w:
          for epd in list(tmp.keys()):
              w.write(f'{epd}\n')
  
  # Start
  pgnfile = 'wchcand22.pgn'
  # download: https://theweekinchess.com/assets/files/pgn/wchcand22.pgn
  genpos(pgnfile)
  
  ```
  
  ### Output
  
  ```
  1r4r1/5p1k/p2p1qQp/2b1nPp1/p7/6RP/B1R2PPK/2B5 b - -,5
  1r4r1/5p1k/p2p1q1p/2b1nPQ1/p7/6RP/B1R2PPK/2B5 b - -,48
  1r4r1/5p1k/p2p1q1p/2b1nPp1/p6Q/6RP/B1R2PPK/2B5 b - -,48
  1r4r1/5p1k/p2p1q1p/2b1nPp1/p5Q1/6RP/B1R2PPK/2B5 b - -,46
  1r4r1/5p1k/p2p1q1p/2b1nPp1/p7/5QRP/B1R2PPK/2B5 b - -,47
  
  ```
  
  The 5, 48 ... are the legal moves from the given positions.
  Test your engine with those legal moves.
  
  
  ---
  
  