alt Hacker News>the complexity of chess is not as high as we think, and that there exist a neural network of less than 10B float32 weights which can encode perfect play.
That is certainly not the mainstream view, so you will have to support your conjecture by some evidence if you would like to convince people that you are right (or demonstrate it empirically end-to-end).
Replies
jibal • last Monday at 8:31 PM
But ... but ... it's his conviction.
My conviction is based on the interesting phenomenon of game tree collapsing.
When you get better at the game, the number of "candidate" moves you need to explore goes down. For example when you are naive at chess you need to explore all legal moves, and then all legal moves response to these moves. The number of nodes in this tree grows exponentially, and the tree depth is rather limited to a small depth.
But when your list of "candidate" move is reduced to size 1. The number of nodes in the tree is equal to its depth. You can "unroll the line very cheaply". (That's the concept of lines in chess. In go that's the concept of "ladders").
When your candidate list is of size 2, the game tree is of size 2^(depth+1).
You can have fractional candidate list size, by only needing to explore down the tree some times, or having the need to explore only 2 candidate some times.
The complexity grows as (Fractional Candidate List Size) ^ (depth + 1 ). With FCLS being between 1 and 2. There is a transition phase which occurs, and allows to go much deeper in the game tree which simplify things and make things tractable (because you then reach endgame tables or an equivalence class number (aka you don't necessarily know the result yet you just know it will be the same result as all these other types of games) ).
So your function is allowed to have a smaller inner function called recursively to explore the game tree of candidate moves within a computational budget, to help make a decision. The upper function resolve the equivalence number to their "win" "draw" "lose" value always in the same way and takes the appropriate maximum (remember your network only goal is to be always consistent).
The better your network get at managing his computational budget the deeper it can go. You can think of it as a version of alpha-beta pruning with improving heuristics.