Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There is another closely related field that has plenty of real applications: formal verification. Essentially the task is to ensure no reachable state violates some property. The problem is the same as in chess, the reachable state space is enormous. There is probably more funding available for this take on the problem than chess, but it has been studied for decades and there are no easy answers.


Out of curiosity, I wonder how long it'll be before we can simply compute every possible valid game, inserting every valid move into some type of tree structure, and have a computer simply walk the tree structure always aiming for a "win" leaf.

Anybody have any ideas on how big the data for that would be? (I suspect there could be some optimizations as some games that start differently could end up in the same state as some other games -- i.e. optimize for board state collisions).


It's possible we never will. Although we take Moore's law for granted, eventually we'll hit the natural limits of computation and storage per m^3, and solving chess completely may well be beyond that (but maybe not, as well).

From Wikipedia (http://en.wikipedia.org/wiki/Shannon_number):

"Allis also estimated the game-tree complexity to be at least 10^123, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^79 and 10^81."


I'm wondering if that number is for every possible game valid or invalid, or just valid games.

In case anybody is interested

http://en.wikipedia.org/wiki/Solved_game


Unless quantum computing pays off in unexpected ways I would wager 'never'.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: