1

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?

13
  • 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. Jul 1, 2022 at 19:27
  • 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.
    – Cort Ammon
    Jul 1, 2022 at 19:58
  • 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.
    – Cort Ammon
    Jul 1, 2022 at 19:58
  • 1
    @TonyEnnis I’m writing a chess engine in c. My question is not regarding choosing moves, it’s about choosing positions. Jul 2, 2022 at 8:21
  • 2
    @TonyEnnis I want to be able to generate seemingly random positions to do perft bench marks for a lot of different positions very fast. Jul 3, 2022 at 15:28

2 Answers 2

3

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.

3
  • 2
    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? Jul 1, 2022 at 21:35
  • @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...
    – AakashM
    Jul 7, 2022 at 13:51
  • @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.
    – Cort Ammon
    Jul 7, 2022 at 15:12
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.

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.