I’d do a search on the first question if I could, but since all three names for the game are under four letters, it won’t work on the SDMB search. And while we’re at it, I might as well ask the chess question too. Anyways, how many possible unique situations can come about in each of the two said games? I’d imagine an exact number would be impossible to determine for Go, but is there a known, exact, number of unique games for chess? I’d also be pretty interested in seeing how one would calculate the numbers.
Chess can be infinitely long, if the players are dumb enough. There’s a rule (as I remember) that exactly the same move taken three times by both players ends the game in draw, but there are plenty of situations where several moves are repeated, and that’s not a draw situation.
And if for some weird reason the players didn’t want to end the game, they could easily do so.
I think the rule is that whenever the game reaches the exact same “position” 3 times, it is declared a stalemate. “Same position” means that the game is in the same state, with the same choices available, and so includes whose-turn-is-it, can-the-players-still-castle, en-passant-is-available.
Since there are only a finite number of possible positions, the length of the game is finite.
I have vague memories of reading that the total number of chess games is on the order of 10^200, but I couldn’t tell you where that came from. (Or was it 10^230?)
Yes, Neptune, I had the “three times” rule wrong. I was only familiar with the simplest cases. I’ll just note, en passant, that the number of games where the players are trying to not to win is vastly larger than the number that would occur under normal play. Which makes life a lot easier for computer programs.
Yes, Neptune, I had the “three times” rule wrong. I was only familiar with the simplest cases. I’ll just note, en passant, that the number of games where the players are trying to not to win is vastly larger than the number that would occur under normal play. Which makes life a lot easier for computer programs.
I seem to remember that Go is played on a 19×19 board. Is that right? If so, then there are 361 positions, meaning that we can place an upper limit of 361! on the number of different Go games. 361! is about 10[sup]768[/sup]. The actual number will be less than this, but how much less I’m not sure offhand.
Go games can be infinitely long - after a piece is removed from the board, you can place another one there in it’s place. There is a rule against having a pair of moves that results in the same position, is there one if there’s two or more situations where this could happen and the players switch between them?
J. E. Littlewood, in his Littlewood’s Miscellany, considers the problem of determining bounds for the number of possible games of chess ( or similar games). He shows that the number of games of chess is at most 10[sup]10[sup]70.5[/sup][/sup] and remarks that the problem of determining a lower bound which is not hopelessly inadequate seems rather difficult. The book was printed in 1986 and I do not know if any subsequent work has been done on the problem.
ryoushi
Most rules disallow any repetition of the positions on the board (either that, or the game is considered a draw), so Go would also be finite.
Oh, and here are some estimates on the number of possible Chess/Go games:
The number of possible formations of stones would not be 361! because this is not a permutation problem. A more accurate upper bound might be to consider that each of those 361 points might have a white stone, a black stone or empty space on it, leading to 3[sup]361[/sup], or about 10[sup]172[/sup]. The number of possible games will be far less, as most of those formations are not conceivable end games, and many of them will be illegal (captured stones still on the board).
Cabbage’s post crossed mine, and claims an estimate of 4.63 * 10[sup]170[/sup] board positions, which suggests that about 1 in 50 of the possible arrangements of stones is a tenable board position. Actually, I’m mildly surprised it’s that high.
Wolfram didn’t seem to have it (in the section linked to by Cabbage) but does anyone know anything about the number of possibilities for Shogi? Although there are no draws, I think there are impositions on repetition (automatic loss for the moving player) so it should be finite.
Though there are probably far more “not trying to win” games than in Chess, I would think the number of “useful” games to be a much smaller percentage of the total than with Chess.
[For those unfamiliar, the game is played on a 9 x 9 board and is related to Chess. Though many of the pieces can’t move more than one square, captured pieces may be ‘dropped’ back into play for the side that captured it – thus if one is holding a captured piece the number of potential moves is very high.]
For Go, you really can’t just go with the number of points on the board. Remember that two important rules are that a stone must have a liberty after play and that a survivable group must have two separated liberties within it.
Yes, but that’s just positions. There is more than one way to get to any given position, is there not? And those different ways of getting there would be considered different games.
True, and I should have been clearer about that and not used the word “games”. But the OP said “Anyways, how many possible unique situations can come about in each of the two said games?” The situation at a given board position is the same no matter how you arrived at it, at least for modeling purposes (it might NOT be the same when you factor in psychology).
If a position is repeated 3 times with the same player to move and the same legal moves are available*, then the player to move can claim a draw by repetition (he doesn’t have to).
*if, for example Black could castle in the first position, and he moves his king away and back, then it’s not the same position.
I’ll ask John Littlewood where he got his estimate.
Fox and James ‘Complete Chess Addict’ give maximum length of a chess game as 5,949 moves.
They comment that the number of chess positions after 2 moves each is 71,852, but that including possible en passant captures bumps it up to 72,084.
They claim number of legal positions as 2x10(43) - sorry, forgot how to do subscript)
Oh, and, of course there are symettries involved here - for instance, a given board position rotated or flipped about an axis is the same “situation” (at a higher level, we have to question what comprises identical “situations” and things get very complex). I’d be moderately curious if the figure quoted in the Wolfram link attempted to account for this. If not, at least divide it by 8[sup]1[/sup] (it’s just an estimate, and the number of positions which are already symettric about one of the board axes and unchanged by some rotation/flipping is going to be very small).
[sup]1[/sup] - symettries of the square, the number of ways you can flip or rotate the board.
yabob: Chronos is correct - I was counting different Go games and not different Go arrangements. Rereading the OP, I think it’s not clear on this point, and I should have specified. Anyway, I didn’t know about the more subtle placement rules, or about removing pieces (I always lose long before that point) so I didn’t factor those in. I also thought about symmetries, but do we want to count these as different arrangements or not? What about setups that don’t touch any of the four sides but are translated from another setup?
On re-reading my original post, indeed, it is quite unclear since I swapped situations/games and chess/go a couple times. Anyways, I was actually asking two (well, four, actually) different questions, and, in my defense, it was late :D.
Anyways, it should have read more like this (changes are in brackets):
Sorry for the confusion.