Comment by calhoun137 | Hacker News Reader

Comment by calhoun137 | Hacker News Reader

Parent Full thread

I am 1000x more interested in chess engine's and "a search for some maximum of abstract skill" than I am in getting good at chess. During my research into this topic I discovered many facts which led me to conclude that there exist multiple chess strategies which humans can use which are currently unknown and which are far more powerful than anything currently used by grand masters or chess engines. This was all before alphazero was released, and I feel strongly that alphazero proved the hypothesis that chess strategy theory will continue to improve and there is still so much to learn.

Chess theory is "always getting better". This is because chess has the property that the skill curve is so extreme and the game so deep that it is seemingly always possible to continue to improve and find new ideas.

Chess engines play a fundamental role in modern human chess. There is a causal relationship between the state of the art in chess engines and the play styles of the top pro's. This is because better engines can find new idea's in positions previously thought to be completely explored. It happened recently with an alphazero game in a spectacular way iirc

There is a theorem which says that given any chess engine, it's impossible to decide if that chess engine is playing in an optimal way. So when you say "in terms of the likelihood of being the best-performing entity at that game", I think its important to be very precise about what we mean, even though in spirit I agree with that statement =)

I started working on a project to build a chess engine that is specifically designed to beat other chess engines by playing in a non-optimal way specifically tailored to find and exploit bugs in the opposing chess engine code/flaws in its algorithm.

I also once proved that any chess engine based on the principles of stockfish will necessarily contain positions where it can be exploited into making bad moves. If you fixed the algorithm to make it not exploitable in that specific position, the theorem says there would exist another position where it would be exploitable. This is what I call the theory of "exploitative chess engines" (in the sense of maximizing the possible gain), as opposed to ones which attempt to play in an "optimal" way (minimizing the maximum loss)

> There is a theorem which says that given any chess engine, it's impossible to decide if that chess engine is playing in an optimal way.

Careful with that formulation.

https://en.wikipedia.org/wiki/Rice%27s_theorem

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

Several major strategy games, notably checkers, have been formally solved. That does make it possible to prove that some engines for those games behave in an optimal way (although it would still be impossible to verify whether an arbitrary program is equivalent to an optimal engine, because the arbitrary program could do something else first whose outcome couldn't be foreseen by the optimal-engine detector).

Although chess has a higher branching factor and a greater depth in various ways than games that have been solved, nobody has found a theoretical barrier to solving it, which in turn means that we can't rule out the possibility of a proof that a particular engine is optimal.

From the formal computation theory standpoint, the situation is even more extreme: the game tree given the threefold repetition rule is finite, which means that we can immediately write down an explicit game tree brute force engine which is guaranteed to perform optimally in every position. This is probably just a handful of lines of code! While this engine can't actually make a single move in a human timescale, from an algorithmic point of view it plays perfectly and we can be sure of that.

The theorems on undecidability of program behavior don't include time constraints like this because they're established using models of computation like Turing machines, where physical limitations of real computing devices are no issue.

I guess the word "theorem" is a little strong, since it depends on the real world. I stand by the statement that it's literally impossible to decide this in practice. If we are allowed to say in a few lines of code you could formally compare any chess engine to a theoretically optimal one, then obviously it is possible to decide by just comparing.

Without being allowed to compare a given engine to a theoretically optimal one which is based on brute forcing the full game tree, and being careful about the problem statement, I suspect it would be possible to prove something along these lines

I would argue something like: "Gods evaluation function" takes as input a chess position and returns whether the position is a forced win, lose, or draw. The rules of chess are so complicated that to go from a continuous evaluation function to a discrete one like that would require an infinite number of steps (this last statement is the one that needs to fleshed out)

I will stop calling it a theorem until I remember why I started calling it that. This situation exists in many non-linear optimization problems, a subject I find really interesting, and in many cases in practice there is no way to decide if a given solution is optimal. For some reason I thought there was a theorem in non-linear optimization theory that was directly relevant here

I agree with all your comments about the non-linearity that is extremely obvious in chess is not captured in the current engines everyone uses, which does lead to all the draw's we are seeing. I'm interested in your results from your engines when they're complete!

Reply on news.ycombinator.com