The Next Big Thing in Computer Chess?

[Ras]

usually gets you close to the "correct" solution

In chess, one bad move easily outweighs 20 good ones in a row, hence losing the game. "Usually" would need to be a very high standard, as in, doesn't usually happen over several complete games. Given that chess is also a very tactical game, about the only solution how a 1-ply could achieve that would be via storing the positions like in endgame tables. Mostly at least, somewhat compressible via lumping "irrelevant" variations of the same position together.

[towforce]

Given that chess is also a very tactical game, about the only solution how a 1-ply could achieve that would be via storing the positions like in endgame tables. Mostly at least, somewhat compressible via lumping "irrelevant" variations of the same position together.

Moving from hand-crafted evaluations to NNs boosted elo by many hundreds of points - despite the immense slowdown in evaluation time.

Therefore, hand-crafted evaluation developers missed some very important things about chess in their coding.

We also know that some quality knowledge more than makes up for a MASSIVE reduction in search space.

We also now know that AlphaGo type Go programs have some immense, and really important, gaps in their knowledge - enough to enable a middling Go player who was trained to exploit them to beat these programs without computer assistance.

We are very far from having captured all the knowledge, and we don't know what knowledge the NNs have that makes them so good.

As discussed previously, the evidence suggests that chess, like other games, has some underlying patterns which, if uncovered, would actually make it surprisingly easy to play very good chess.

[syzygy]

Larry Kaufman mentioned in another post 97% draws between SF 16 and SF 15 with 2"+1' TC in a 620 games match with standard opening and 2 threads, he estimated 99% draws for Rapid TC. How much Elo is still to gain on CCRL Blitz? Time's running, finish line in sight.
--
Srdja

Engines need to use selective search in order to cause the opponent to fall to designed traps and this is not the way they work today.

If you want to find what is possible to achieve you need to build anti-stockfish engine when the target is beating stockfish when you get more time.

Anti-stockfish with white is going to work in the following way:
For white search every possible legal move but for black do not search every possible legal move but simply calculate the move that stockfish is going to play and prune the rest of the moves.

After part of your time(for example half of the target time but maybe different percentage is optimal) you do not calculate stockfish's moves because calculating stockfish's move is too expensive but you remember the stockfish's moves that you already calculated in order to prune the rest of the moves in your search.

In this way the engine may prefer lines when stockfish does mistakes so there is a bigger probability to win and the question is what is the percentage of wins that you can get against stockfish 2''+1' TC in this way(I guess clearly more than using unequal time control).

So you basically suggest to give one player more time and outsearch the other engine, this is based on the assumption that there is still something to find via the outsearch approach.....the effective branching factor of ~1.25 of modern SF indicates that there is not much to search anymore nowadays, or alike.

I understand the suggestion as an attempt at opponent modeling. You assume SF as opponent will play SF moves (reasonable assumption) and specifically look for moves to which the SF response happens to be poor. Of course to do this you'll have to calculate the SF moves with a very limited depth, which will give you no guarantee that your real SF opponent will play these same moves.

The way to make it work is to do this when creating an opening book. But it is risky. If you play an objectively weak move because you have noticed in your preparation that SF responds with a still weaker move, you don't have a guarantee that your real SF opponent will play that same still weaker move. Multithreaded search is not deterministic, SF may have been updated, and your opponent may have a book itself, etc.

If your opponent is a fully deterministic engine, then I do not doubt that with enough trial and error you can find a sequence of moves that give you a win, and when you win once, you win every time.

[towforce]

So you basically suggest to give one player more time and outsearch the other engine, this is based on the assumption that there is still something to find via the outsearch approach.....the effective branching factor of ~1.25 of modern SF indicates that there is not much to search anymore nowadays, or alike.

That might be what Uri meant, but for me, there's another way. In Go, the top programs use basically the same method as AlphaGo (a big and really well trained NN). We had believed that these Go programs are now well beyond the capability of a human to beat - but we now now that to be false: a team uncovered some truly shocking gaps in their knowledge, and using this information, a middling human player (Kellin Pelrine) was able to decisively beat KataGo without computer assistance. IMO, it's likely that Stockfish's NN has gaps in its knowledge as well. Maybe even LC0 does.

Caveat: what worked in Go might not work in chess, because of search: because chess has a massively lower branching factor than Go does, search alone can hide a lot of weaknesses. However, there's still a chance that glaring weaknesses in the evaluation can be exploited IMO.

[smatovic]

[...]

[...]

[...]
The way to make it work is to do this when creating an opening book. But it is risky. If you play an objectively weak move because you have noticed in your preparation that SF responds with a still weaker move, you don't have a guarantee that your real SF opponent will play that same still weaker move. Multithreaded search is not deterministic, SF may have been updated, and your opponent may have a book itself, etc.
[...]

In some kind of sense we already have such a thing with unbalanced opening books. You "lay a trap" with an unbalanced opening and the engine has to find a way out of the disadvantage again.

--
Srdja

[smatovic]

....maybe to summarize (biased) what people mentioned in this thread as next thing:

- PAB/NNOM - Predicator AlphaBeta, Move Ordering Neural Networks, a neural net driven AB search
- Super-AI - an AI coding a chess engine and outperforming humans in this task
- new programming paradigm in chess, to utilize CPU+SIMD+GPU+TPU+HBM via unified memory
- chess variants, move on to other, non-drawish, chess variants
- incremental progress, there is enough to gain, via incremental progress of software+hardware
- 8-men EGTB
- GUI, advances in GUIs for the user
- human-opponent-play, develop chess engines to maximize user experience
- God's Algorithm for Chess, find an algorithm which plays perfect chess
- knowledge base vs. neural networks, store chess knowledge in graphs instead of neural networks

--
Srdja

[towforce]

....maybe to summarize (biased) what people mentioned in this thread as next thing:

- PAB/NNOM - Predicator AlphaBeta, Move Ordering Neural Networks, a neural net driven AB search
- Super-AI - an AI coding a chess engine and outperforming humans in this task
- new programming paradigm in chess, to utilize CPU+SIMD+GPU+TPU+HBM via unified memory
- chess variants, move on to other, non-drawish, chess variants
- incremental progress, there is enough to gain, via incremental progress of software+hardware
- 8-men EGTB
- GUI, advances in GUIs for the user
- human-opponent-play, develop chess engines to maximize user experience
- God's Algorithm for Chess, find an algorithm which plays perfect chess
- knowledge base vs. neural networks, store chess knowledge in graphs instead of neural networks

--
Srdja

+1 always good to have a summary

[Uri Blass]

Larry Kaufman mentioned in another post 97% draws between SF 16 and SF 15 with 2"+1' TC in a 620 games match with standard opening and 2 threads, he estimated 99% draws for Rapid TC. How much Elo is still to gain on CCRL Blitz? Time's running, finish line in sight.
--
Srdja

Engines need to use selective search in order to cause the opponent to fall to designed traps and this is not the way they work today.

If you want to find what is possible to achieve you need to build anti-stockfish engine when the target is beating stockfish when you get more time.

Anti-stockfish with white is going to work in the following way:
For white search every possible legal move but for black do not search every possible legal move but simply calculate the move that stockfish is going to play and prune the rest of the moves.

After part of your time(for example half of the target time but maybe different percentage is optimal) you do not calculate stockfish's moves because calculating stockfish's move is too expensive but you remember the stockfish's moves that you already calculated in order to prune the rest of the moves in your search.

In this way the engine may prefer lines when stockfish does mistakes so there is a bigger probability to win and the question is what is the percentage of wins that you can get against stockfish 2''+1' TC in this way(I guess clearly more than using unequal time control).

So you basically suggest to give one player more time and outsearch the other engine, this is based on the assumption that there is still something to find via the outsearch approach.....the effective branching factor of ~1.25 of modern SF indicates that there is not much to search anymore nowadays, or alike.

--
Srdja

Yes
I suggest to give one engine more time but not only to do it but to use special search that help to go to positions that the opponent is going to play wrong because I believe that it is possible that normal alphabeta is not enough and you need to try to find a position that the opponent is going to make a wrong moves so selective search may help.

The effective branching factor of ~1.25 suggest that stockfish is pruning a lot of lines.
Of course usually it prune the bad lines but maybe it prune also some good lines.

[towforce]

Point is, to find such an algorithm you will need a lot of CPU time and a lot of memory, doubt you can do it in your mind alone, I guess you tried

If there is a "good" solution to chess in linear space, it would probably be relatively easy to find. A good solution is likely to be non-linear, though.

I came up with "straight lines will work" - but they will only work for parts of the model which are close together - and it seems likely that some parts of the model would be far apart.

Your answer (quoted above) prompted me to have an idea - something I'm calling "compatible lines". I will reinvestigate...

Looks as though my "compatible lines" idea is mathematically sound (the cost is making the initial model bigger - but hopefully not the final algorithm). I am excited and actively working on the idea again!

[smatovic]

...
I am excited and actively working on the idea again!

enjoy the ride.

--
Srdja