Hacker News Reader

Comment by e12e | Hacker News Reader

I don't understand this quote: "[determining the number of valid positions is] sadly unattainable for Chess, where determining if a given position is legal is the essence of a class problems known as Retrograde analysis.".

Is this due to some subtle distinction between valid moves/games and positions? Because since the starting position is given, and the rules are set, surely it's possible (in theory) to simply emulate all possible moves, and recording positions as one goes along, backtracking on cycles [ed: and on check mate]?

View on HN

It seems that in chess, the (current) "best" way to figure out whether a move was legal is through retrograde analysis (1). As you can imagine, this becomes very expensive, very fast. Not only that, but the current position may be legal in chess given some previous conditions, but illegal given others (consider Castling). Therefore, given no extra information, you may not be able to tell whether a given chessboard is legal without being given the entire history of the board as well.

Disclaimer: I don't know what I'm talking about, just googled retrograde analysis

1. http://en.wikipedia.org/wiki/Retrograde_analysis

I'm not sure what ruleset OP is using for their analysis, but with superko in place you would also need the entire history of the board to know if a move is valid.

Although rulesets might differ on what is considered a legal move, they all agree on what is a legal position: one where every connected group of stones has liberties (empty adjacent point). Furthermore, in all rulesets you can reach any legal position by playing legal moves (and passes) from the empty starting position.

Right. So unattainable means "not feasible", not impossible - or that it's not possible to enumerate all legal positions. I of course realize that simulating all possible games (ignoring cycles) would be very demanding.

Chess has state; it is not a simple function of board layouts. Whether or not it is valid to make moves such as castling or en passant pawn capture is dependent on the move order, not on the current board position.

A position is valid iff there is a squence of legal moves that leads to it. In go, a legal turn consists of putting a stone on nearly any vacant point (some rule sets prohibit suicide moves, and all prohibit exactly repeating the position at the end of your previous turn) or passing (not putting a stone, which normally happens only near the end of the game), so the only illegal board configurations are those that have groups with no adjacent vacant points ("liberties"). In chess, these moves are more constrained: each piece may move only certain directions, sometimes depending on the locations of opposing pieces.

http://senseis.xmp.net/?Liberty

http://senseis.xmp.net/?Suicide

Reply on news.ycombinator.com