5 ms·
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 t
by e12e 12y ago
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]?
- cevn 12y agoIt 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 http://en.wikipedia.org/wiki/Retrograde_analysis
- b3n 12y agoI'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.
- tromp 12y agoAlthough 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.
- e12e 12y agoRight. 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.
- yuubi 12y agoA 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/?Liberty http://senseis.xmp.net/?Suicide http://senseis.xmp.net/?Suicide
- chongli 12y agoChess 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.