> For the chess problem we propose the estimate number_of_typical_games ~ typical_number_of_options_per_movetypical_number_of_moves_per_game. This equation is subjective, in that it isn’t yet justified beyond our opinion that it might be a good estimate.

This applies to most if not all games. In our paper "A googolplex of Go games" [1], we write

"Estimates on the number of ‘practical’ n × n games take the form b^l where b and l are estimates on the number of choices per turn (branching factor) and game length, respectively. A reasonable and minimally-arbitrary upper bound sets b = l = n^2, while for a lower bound, values of b = n and l = (2/3)n^2 seem both reasonable and not too arbitrary. This gives us bounds for the ill-defined number P19 of ‘practical’ 19x19 games of 10^306 < P19 < 10^924 Wikipedia’s page on Game complexity[5] combines a somewhat high estimate of b = 250 with an unreasonably low estime of l = 150 to arrive at a not unreasonable 10^360 games."

> Our final estimate was that it is plausible that there are on the order of 10^151 possible short games of chess.

I'm curious how many arbitrary length games are possible. Of course the length is limited to 17697 plies [3] due to Fide's 75-move rule. But constructing a huge class of games in which every one is probably legal remains a large challenge; much larger than in Go where move legality is much easier to determine.

The main result of our paper is on arbitrarily long Go games, of which we prove there are over 10^10^100.

[1] https://matthieuw.github.io/go-games-number/AGoogolplexOfGoG...

[2] https://en.wikipedia.org/wiki/Game_complexity#Complexities_o...

[3] https://tom7.org/chess/longest.pdf

▲

jmount 9 hours ago | parent | next [-]

Nice stuff, thanks for sharing that.

I remember from a lot of combinatorial problems (like cutting up space with hyper-planes or calculating VC dimension) that one sees what looks like exponential growth until you have a number of items equal to the effective dimension of the system and then things start to look polynomial.

BTW: I was going through some of your lambda calculus write-ups a while ago. Really great stuff that I very much enjoyed.

▲

qsort 9 hours ago | parent | prev [-]

I wonder if/how that interacts with the new draw rule. (For the uninitiated: the formal rule to adjudicate games as draws automatically or on time is that the game is a draw if there exists no sequence of moves that could lead to checkmate. Interestingly, although this has almost no strategic implications, it means that... it's almost impossible to write a program to detect draws that's technically correct. A similar corner case is draws in Magic the Gathering, which is literally undecidable in general.)

▲

Sesse__ 8 hours ago | parent [-]

Is that a new rule? I was under the impression that it had been the case for a very long time that if you went out on time but there was no possible sequence of moves leading to checkmating you, it was a draw instead. (Meaning, of course, that having more pieces could be a disadvantage in such situations, which feels a bit unfair. E.g., KvKB is a draw, but KPvKB can lead to a mate if both sides cooperate, and thus would be a time loss for white even if black would never win in practical play.)

▲

qsort 6 hours ago | parent | next [-]

That's not new, but how it formally works has changed. There used to be a number of explicitly enumerated cases (i.e. bare king and king with a minor piece,) now the rule instead just says that there must exist a sequence of moves to mate. Some positions, even with pawns (imagine a completely closed position with only pawns and kings) wouldn't have been automatically drawn under the previous system but now would be. I think USCF rules, unlike FIDE, still have the enumerated cases?

The difference is extremely minor and has almost no strategic implications, it's just an interesting corner case.

	▲	TZubiri 4 hours ago \| parent [-]
		Does it depend on elo as well?

▲

jmount 7 hours ago | parent | prev [-]

I just updated the article. I did use Python's insufficient material detection, in addition to the ability to call for a draw (3-fold repetition, and 50 move rule). I think the "75 move rule" that doesn't require a player to call is one of the more recent rule changes.