user30006: 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?

user30545: 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.

user6885: 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.

30006: <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>
 30545: <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>
 6885: <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>
