chess programming - predictions for the next 5 years

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Hrvoje Horvatic
Posts: 14
Joined: Mon Nov 10, 2014 12:53 pm

chess programming - predictions for the next 5 years

Post by Hrvoje Horvatic » Sun Feb 03, 2019 2:50 pm

I'm posting my bold predictions, in hope of open, constructive discussion without trashing and trolling... hopefully, you have something to say and have predictions of yours, too...

Right off the bat, let's address A0/leela chess phenomenon. Obviously, they are here to stay... it is practically THE first alternative approach to chess to successfully challenge classical alpha-beta minimax searchers... regardless of the fact that most certainly there were some shady things going on there, regardless of the fact if the A0/leela is/are stronger than Stockfish or not... it is still a success story... I really don't like the fact that the project was initiated and financed by huge multi-billion company with its own agenda, I don´t like the PR around it, the glitter, the claims, I don't like any of it, but the facts are... well, facts! :) A0 and Leela are the success story and that's a fact.

My first (not so bold) prediction is that for the next few years ANN+MCTS engines and classical AB searchers will live and develop in parallel, side by side... no side will clearly dominate... and if you are looking for the definition of the word "dominate", just remember how it looked like when Rybka first showed on the scene... drawing a match with Komodo, and then winning in tie-breaks is not a sign of domination by Leela, it is a sign that it is just a bit better... which is a great accomplishment by itself, if you manage to disregard and tone down the hype, expectations and public opinion around internet today...

My next, much more bold prediction concerns the so-called "hybrid" approaches... I think they will all turn out to be failure... it's pretty strong and bold claim, so let me explain my thinking...

Many people noticed that Leela is much stronger positionally and much weaker tactically, so it was very natural that people without technical background in chess programming would instantly think that if you combine approaches, you would get engine that is ultra strong both tactically and positionally... but things don't work that way... :)

We are talking about 2 different paradigms here, and oil and water don't mix... there are 2 cardinal differences between MCTS/UCT search and AB search (let's ignore ANN part for the moment). the first difference is depth-first versus best-first expansion rule, and the second difference is value backup rule (minimaxing versus "averaging")... you cannot have a little bit of both, you can't just put them together and "combine" them... you need a new paradigm, a new approach that will INTEGRATE them, a new over-arching idea... all the ideas where you use AB for "probing", either at he root or at the leaves will not work... all the approaches combining values of minimaxing and MCTS at the node MUST be worse than each in isolation... tactical and strategic thinking are completely different, you can't "mix" them... MCTS/UCT is good for strategic thinking, because "averaging" backup rule is almost direct translation of strategic thinking into computation... in strategy, you choose move that is good "on average", regardless of what your opponent does... you don't chase the "best" move, because there ain't none... actually this reminds me of a funny one-liner that says "strategy is knowing what to do, when there is nothing to do"... :) this is diametrically opposite of how tactics works and how minimaxing works, choosing only one "best" move... how could you just "mix" this an hope it will somehow turn out right?

Let's look for a moment how a human GMs solve this problem... granted, bringing humans into argument will not resonate well with some of you that read this, but I don't look at humans as humans, but as a chess-playing agents with limited resources and weak hardware that have solved some of the problems that AB searchers and MCTS searchers haven't yet... So if we go back to how humans think for a second, we can see that they clearly separate tactical and strategic thinking... As a chess player, I prioritize tactics, and first thing that I do when I look at the position (after some basic counting and inventory) is activating my "tactics detectors"... are there loose (unprotected) pieces? exposed king? pieces on weird positions? unusual configurations of pieces? if yes, I go into tactical analysis... if not, I go into positional analysis... I don't do both at the same time, and I do not "combine" results, I prioritize them...

I don't want to discourage attempts at "hybrid" approach that are going on right now (Scorpio, Komodo MCTS,...) but it looks obvious to me that they will fail... until there is a new breaktrough, a new paradigm shift... and I don't think it will happen any time soon...

Moving on to my next prediction... let's discuss the direction in which AB searchers will evolve... Most of the improvement in the last 10 years was in the area of search... and the most notable single improvement was introduction of LMR... I think that improvement in the search technology will continue, but will (actually, it already has) hit into diminishing returns wall... now, if everybody hits the same wall and everybody is affected in the same way, it doesn't matter... we all grow slowly together and face the same problems together, it doesn't matter if the results are not proportional to the effort, results are there and only results matter... but if there is an alternative evolutionary line, like MCTS is, then infinitesimally small improvements in search will not matter that much...

so what will matter? how can AB searchers respond to the MCTS challenge?

I think there are basically only 2 ways, and the first is, ironically, improving tactics... the second is obvious, improving evaluation functions, something that should have happened a long time ago, but we were all "blinded by the light", surprised at how well our engines play chess if we only improve search... there was no incentive to put an effort into eval functions... until now... :)

let's address the first point, improving tactics... it seems ironic that I not only suggest but RECOMMEND improving tactics... aren't AB searchers tactical beasts? well, not really... :) what happened was that, once engines bypassed humans in tactics, their tactical sharpness started to degrade... adding all those search improvements made engines more and more tactically blind... but it payed ELO-wise, because they traded missing some tactical shot for getting more depth and being better positionally... and it was a good trade off... that is, until now... think about it, if every engine gradually started to be more blind, and all of them did it in parallel, and there was no other chess entity that could exploit that, there was only upside, there was no downside... there was no one-eyed king to rule in the land of the blind... but of course, things have now changed, and the opponent is TRULY terrible at tactics, and you get most "bangs for the bucks" if you get good at it... getting additional plies will not help AB searchers that much, but exploiting tactical oversights made by A0/Leela will... and since A0/Leela can't get better at tactics, this is your quickest route to their heart...

so my bold prediction is that AB searchers will become much better at tactics, they will prune and reduce much more carefully, and search will become much sharper, because it will pay off... in fact, in short term it is the only thing that will pay off against A0/Leela...

Looking at the things long term, AB searchers will either improve their evaluation functions, or they will die out, just like dinosaurs... I think that the beginning of the trend is here, and it started with the popularization of so-called "Texel tuning" method... I think it was a small step for Texel, but it could be a large one (or the first one) for the AB searchers... :) a nudge in the right direction... :)

I have a few more things to say, but this post already became too long, so I will stop now... maybe we can continue discussion after... you present your predictions? :P

Daniel Shawul
Posts: 3603
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: chess programming - predictions for the next 5 years

Post by Daniel Shawul » Sun Feb 03, 2019 3:44 pm

I'm posting my bold predictions, in hope of open, constructive discussion without trashing and trolling... hopefully, you have something to say and have predictions of yours, too...
I welcome you our mesiah :)
Right off the bat, let's address A0/leela chess phenomenon. Obviously, they are here to stay... it is practically THE first alternative approach to chess to successfully challenge classical alpha-beta minimax searchers... regardless of the fact that most certainly there were some shady things going on there, regardless of the fact if the A0/leela is/are stronger than Stockfish or not... it is still a success story... I really don't like the fact that the project was initiated and financed by huge multi-billion company with its own agenda, I don´t like the PR around it, the glitter, the claims, I don't like any of it, but the facts are... well, facts! :) A0 and Leela are the success story and that's a fact.

My first (not so bold) prediction is that for the next few years ANN+MCTS engines and classical AB searchers will live and develop in parallel, side by side... no side will clearly dominate... and if you are looking for the definition of the word "dominate", just remember how it looked like when Rybka first showed on the scene... drawing a match with Komodo, and then winning in tie-breaks is not a sign of domination by Leela, it is a sign that it is just a bit better... which is a great accomplishment by itself, if you manage to disregard and tone down the hype, expectations and public opinion around internet today...

My next, much more bold prediction concerns the so-called "hybrid" approaches... I think they will all turn out to be failure... it's pretty strong and bold claim, so let me explain my thinking...

Many people noticed that Leela is much stronger positionally and much weaker tactically, so it was very natural that people without technical background in chess programming would instantly think that if you combine approaches, you would get engine that is ultra strong both tactically and positionally... but things don't work that way... :)
I disagree completely. It is very easy to fix tactical blindess of the MCTS searcher -- even without going deeper into the tree and only staying at the root. What I do is spend, say, 20% of the time doing a multi-pv alpha-beta search and 80% doing MCTS with neural nets. The MCTS is done after the alpha-beta so the AB score is fed as a prior score to guide the MCTS search. So in the PUCB formula the average score is 0.2*AB+0.8*MCTS.
If you have some blunder move at the root then it won't be selected often. The prior is not decayed by the number of visits (unlike the policy prior),
so what AB identifies as a blunder will remain so for the remainder of the search. Scorpio NN never makes blunders because of this.

Take this example for BT2450.epd where the best move is Bxb6. Alpha-beta searchers find it fast but MCTS has problems.

[D] 6k1/2b2p1p/ppP3p1/4p3/PP1B4/5PP1/7P/7K w - - 0 1

Search starts with AB

Code: Select all

# Searching root moves with alpha-beta
# Finished with depth 25 in 5563ms
# [st = 10056ms, mt = 26465ms , hply = 0 , moves_left 10]
63 101 100 19409  Bd4-f2 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 Bf2-e3 Kd6-d5 Kg2-f2 Kd5-c4 Kf2-e2 Kc4xb5 Ke2-d3 Kb5xc6 Kd3-c4
64 100 201 40193  Bd4-f2 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 f3-f4 e5-e4 Kg2-f1 Kd6-d5 Kf1-e2 Kd5-c4 Ke2-e3 f7-f5 Ke3-e2 Kc4xb5 Bf2-
....
The hybrid result

Code: Select all

# Move   Value=(V,P,V+P)   Policy  Visits                  PV
#----------------------------------------------------------------------------------
#  1   (0.642,0.523,0.582)  29.06   45851   Bd4-e3 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 f3-f4 Kd6-d5 f4xe5 Kd5-c4 Be3-f4 Kc4xb5 e5-e6 f7xe6 Bf4xc7 Kb5xc6 Bc7-d8 b6-b5 Kg2-f3 b5-b4 Kf3-e4 b4-b3 Ke4-d3 Kc6-d5 Kd3-c3
#  2   (0.518,0.476,0.497)  15.92    2334   Bd4-c3 b6-b5 a4xb5 a6xb5 Kh1-g2 Kg8-f8 f3-f4 e5xf4 g3xf4 Bc7xf4 Bc3-f6 Kf8-e8 Kg2-f3 Bf4xh2 Kf3-e4 h7-h5
#  3   (0.615,0.562,0.588)  13.83   63755   Bd4-f2 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 f3-f4 e5-e4 g3-g4 Kd6-d5 f4-f5 Kd5-c4 Bf2-g3 Bc7xg3 Kg2xg3 Kc4xb5 c6-c7 Kb5-c6 c7-c8=Q Kc6-b5 Kg3-f4
#  4   (0.523,0.486,0.504)   9.51    1518   Bd4-b2 b6-b5 a4xb5 a6xb5 Kh1-g2 Kg8-f8 f3-f4 e5xf4 g3xf4 Bc7xf4 Bb2-f6 Kf8-e8 Kg2-f3 Bf4xh2 Kf3-e4
#  5   (0.623,0.549,0.586)   6.53   17781   Bd4-g1 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 Bg1-e3 Kd6-d5 f3-f4 Kd5-c4 f4xe5 Kc4xb5 Kg2-f3 Kb5xc6 Kf3-e4 b6-b5 Be3-d2
#  6   (0.205,0.079,0.142)   6.09     218   b4-b5 a6xb5 a4xb5 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e2 Ke7-d6 Ke2-d3 Kd6-c5 f3-f4 Kc5xb5
#  7   (0.165,0.137,0.151)   3.40     125   Bd4xe5 Bc7xe5 b4-b5 a6xb5 a4xb5 Kg8-f8 Kh1-g2 Kf8-e7 f3-f4 Be5-c7 Kg2-f3 Ke7-d6 Kf3-e4
#  8   (0.547,0.471,0.509)   3.02     509   Bd4-a1 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-e6 Kg2-f2 Ke6-d5 Kf2-e3 f7-f5
#  9   (0.290,0.979,0.635)   2.92   65472   Bd4xb6 Bc7xb6 a4-a5 Bb6-c7 b4-b5 a6xb5 a5-a6 Bc7-b6 c6-c7 Bb6xc7 a6-a7 b5-b4 a7-a8=Q Kg8-g7 Qa8-b7 Bc7-d6 Kh1-g2 h7-h5 Qb7-d5 Bd6-e7 Qd5xe5 Be7-f6 Qe5-b5
# 10   (0.101,0.050,0.076)   2.76      87   f3-f4 e5xd4 Kh1-g2 Kg8-f8 Kg2-f3 Kf8-e7 Kf3-e4 Ke7-d6 Ke4xd4 Kd6xc6 Kd4-c4 b6-b5
# 11   (0.065,0.050,0.058)   2.30      70   Kh1-g2 e5xd4 Kg2-f2 Kg8-f8 Kf2-e2 Kf8-e7 Ke2-d3 Ke7-d6 Kd3xd4 Kd6xc6 Kd4-c4 h7-h5 b4-b5
# 12   (0.149,0.051,0.100)   2.13      70   a4-a5 e5xd4 a5xb6 Bc7xb6 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e2 Ke7-d6
# 13   (0.109,0.040,0.074)   1.09      34   Bd4-c5 b6xc5 b4xc5 Kg8-f8 Kh1-g2 Kf8-e7 Kg2-f2 Ke7-e6 Kf2-e3
# 14   (0.051,0.040,0.045)   0.61      18   g3-g4 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e2
# 15   (0.126,0.050,0.088)   0.30       9   Kh1-g1 e5xd4 Kg1-f2 Kg8-f8 Kf2-e2 Kf8-e7
# 16   (0.085,0.047,0.066)   0.24       7   h2-h4 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7
# 17   (0.098,0.040,0.069)   0.20       6   h2-h3 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7
Pure MCTS result

Code: Select all

# Move   Value=(V,P,V+P)   Policy  Visits                  PV
#----------------------------------------------------------------------------------
#  1   (0.622,0.000,0.622)  29.06  147106   Bd4-e3 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 f3-f4 e5-e4 f4-f5 Kd6-d5 f5xg6 h7xg6 Be3-f4 Bc7xf4 g3xf4 Kd5-d6 Kg2-f2 f7-f5 Kf2-e3 Kd6-c7 Ke3-d4 Kc7-d6 h2-h4 Kd6-c7 Kd4-e5 e4-e3 Ke5-e6 e3-e2 Ke6-f7
#  2   (0.514,0.000,0.514)  15.92    2724   Bd4-c3 b6-b5 a4xb5 a6xb5 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e3 Ke7-d6 Ke3-e4 f7-f5 Ke4-d3 Kd6xc6 h2-h3 Kc6-d5
#  3   (0.620,0.000,0.620)  13.83   46891   Bd4-f2 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 f3-f4 e5-e4 g3-g4 Kd6-d5 f4-f5 Kd5-c4 Bf2-g3 Bc7xg3 Kg2xg3 Kc4xb5 c6-c7 Kb5-c6 c7-c8=Q Kc6-b5 Kg3-f4
#  4   (0.516,0.000,0.516)   9.51    1650   Bd4-b2 b6-b5 a4xb5 a6xb5 Kh1-g2 Kg8-f8 f3-f4 e5xf4 g3xf4 Bc7xf4 Bb2-f6 Kf8-e8 Kg2-f3 Bf4xh2 Kf3-e4
#  5   (0.620,0.000,0.620)   6.53   24020   Bd4-g1 Kg8-f8 b4-b5 a6xb5 a4xb5 Kf8-e7 Kh1-g2 Ke7-d6 f3-f4 e5xf4 g3xf4 Kd6-d5 Kg2-f3 Kd5-c4 Kf3-e4 Kc4xb5 Ke4-d5 Bc7xf4 Bg1-d4 Bf4xh2 Bd4-f6
#  6   (0.202,0.000,0.202)   6.09     274   b4-b5 a6xb5 Bd4xb6 Bc7xb6 a4xb5 Kg8-f8 Kh1-g2 Kf8-e7 g3-g4 Ke7-d6 g4-g5
#  7   (0.309,0.000,0.309)   3.40     205   Bd4xe5 Bc7xe5 b4-b5 a6xb5 a4xb5 Kg8-f8 Kh1-g2 Kf8-e7 f3-f4 Be5-c7 Kg2-f3 Ke7-d6 Kf3-e4
#  8   (0.525,0.000,0.525)   3.02     574   Bd4-a1 b6-b5 a4xb5 a6xb5 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e3 Ke7-d6 Ke3-e4 f7-f5 Ke4-d3
#  9   (0.447,0.000,0.447)   2.92     314   Bd4xb6 Bc7xb6 b4-b5 a6xb5 a4xb5 Kg8-f8 Kh1-g2 Kf8-e7 g3-g4 Ke7-d6 g4-g5
# 10   (0.077,0.000,0.077)   2.76      95   f3-f4 e5xd4 Kh1-g2 Kg8-f8 Kg2-f3 Kf8-e7 Kf3-e4 Ke7-d6 Ke4xd4 Kd6xc6 Kd4-c4 b6-b5 a4xb5
# 11   (0.070,0.000,0.070)   2.30      78   Kh1-g2 e5xd4 Kg2-f2 Kg8-f8 Kf2-e2 Kf8-e7 Ke2-d3 Ke7-d6 Kd3xd4 Kd6xc6 Kd4-c4 h7-h5 b4-b5
# 12   (0.143,0.000,0.143)   2.13      83   a4-a5 e5xd4 a5xb6 Bc7xb6 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e2 Ke7-d6
# 13   (0.166,0.000,0.166)   1.09      45   Bd4-c5 b6xc5 b4xc5 Kg8-f8 Kh1-g2 Kf8-e7 Kg2-f2 Ke7-e6 Kf2-e3
# 14   (0.066,0.000,0.066)   0.61      20   g3-g4 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7 Kf2-e2
# 15   (0.077,0.000,0.077)   0.30      10   Kh1-g1 e5xd4 Kg1-f2 Kg8-f8 Kf2-e2 Kf8-e7 Ke2-d3
# 16   (0.077,0.000,0.077)   0.24       8   h2-h4 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7
# 17   (0.133,0.000,0.133)   0.20       8   h2-h3 e5xd4 Kh1-g2 Kg8-f8 Kg2-f2 Kf8-e7
(V,P,V+P) = (MCTS, AB, MCTS+AB)
You can see that MCTS is not seeing Bxb6 but the high AB prior of 0.979 is pulling more visits for the move and is eventually played due to its high number of visits. However without AB it just has 314 visits.
Similarly, for blunders that have close to 0 scores the AB prior will force MCTS not to consider often.

I asked tcec if they could have a demo match between Scorpio+With Leela Net+AB at root against Leela+With Same net. If leela makes blunders it would be picked up by this scorpio approach...
We are talking about 2 different paradigms here, and oil and water don't mix... there are 2 cardinal differences between MCTS/UCT search and AB search (let's ignore ANN part for the moment). the first difference is depth-first versus best-first expansion rule, and the second difference is value backup rule (minimaxing versus "averaging")... you cannot have a little bit of both, you can't just put them together and "combine" them... you need a new paradigm, a new approach that will INTEGRATE them, a new over-arching idea... all the ideas where you use AB for "probing", either at he root or at the leaves will not work... all the approaches combining values of minimaxing and MCTS at the node MUST be worse than each in isolation... tactical and strategic thinking are completely different, you can't "mix" them... MCTS/UCT is good for strategic thinking, because "averaging" backup rule is almost direct translation of strategic thinking into computation... in strategy, you choose move that is good "on average", regardless of what your opponent does... you don't chase the "best" move, because there ain't none... actually this reminds me of a funny one-liner that says "strategy is knowing what to do, when there is nothing to do"... :) this is diametrically opposite of how tactics works and how minimaxing works, choosing only one "best" move... how could you just "mix" this an hope it will somehow turn out right?
You decided AB and MCTS dont' mix based on what exactly ? The only reason why A0 used MCTS is because that is the only option given a very slow NN eval. The search has to be very selective just like how humans think. I have tried several backup operators that improve upon pure averaging. These are especially successful with hand written evals that are linear, but still using NN eval a scheme that does "averaging<8000 visits + minmax > 8000 vistis" works best for me. There is not a real need for that to me since the simple approach of mixing AB and MCTS at the root works pretty well for me right now. You can imagine Stockfish doing 20% of the multi-pv AB search and how tactical problems evaporate ..

I have actually tested many hybrid approaches when I didn't have policy network and were using search for it -- but it seems policy network has a lot of
positional knowledge even though it is bad tactically. But the MCTS search corrects this tactical blindeness like a "policy improvement operator".
It is even possible to formulate AB in rollouts form to combine it with MCTS but I don't know how that will fair with a slow NN eval.
So many things to experiment with... so why u so blue ? :)

Let's look for a moment how a human GMs solve this problem... granted, bringing humans into argument will not resonate well with some of you that read this, but I don't look at humans as humans, but as a chess-playing agents with limited resources and weak hardware that have solved some of the problems that AB searchers and MCTS searchers haven't yet... So if we go back to how humans think for a second, we can see that they clearly separate tactical and strategic thinking... As a chess player, I prioritize tactics, and first thing that I do when I look at the position (after some basic counting and inventory) is activating my "tactics detectors"... are there loose (unprotected) pieces? exposed king? pieces on weird positions? unusual configurations of pieces? if yes, I go into tactical analysis... if not, I go into positional analysis... I don't do both at the same time, and I do not "combine" results, I prioritize them...

I don't want to discourage attempts at "hybrid" approach that are going on right now (Scorpio, Komodo MCTS,...) but it looks obvious to me that they will fail... until there is a new breaktrough, a new paradigm shift... and I don't think it will happen any time soon...

jdart
Posts: 3725
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: chess programming - predictions for the next 5 years

Post by jdart » Sun Feb 03, 2019 7:32 pm

If you actually look at how Stockfish got to be at the level it is at now, it was a whole bunch of incremental changes, many of them individually small in magnitude. These included both search and eval changes. It hasn't been one thing. Maybe we will get a real paradigm shift that moves the rating needle a lot .. this happened in Go over some years as new techniques were discovered. But maybe not. Lc0 has made really rapid progress so far but whether it is going to launch programs into a new ratings realm well above Stockfish and the other top A/B engines is yet to be known. We are not there yet IMO.

--Jon

syzygy
Posts: 4411
Joined: Tue Feb 28, 2012 10:56 pm

Re: chess programming - predictions for the next 5 years

Post by syzygy » Sun Feb 03, 2019 8:05 pm

Hrvoje Horvatic wrote:
Sun Feb 03, 2019 2:50 pm
let's address the first point, improving tactics... it seems ironic that I not only suggest but RECOMMEND improving tactics... aren't AB searchers tactical beasts? well, not really... :) what happened was that, once engines bypassed humans in tactics, their tactical sharpness started to degrade... adding all those search improvements made engines more and more tactically blind... but it payed ELO-wise, because they traded missing some tactical shot for getting more depth and being better positionally... and it was a good trade off... that is, until now... think about it, if every engine gradually started to be more blind, and all of them did it in parallel, and there was no other chess entity that could exploit that, there was only upside, there was no downside... there was no one-eyed king to rule in the land of the blind...
I cannot disagree more with what you write here. (So I probably disagree with the rest of your post, too.)

User avatar
cdani
Posts: 2103
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: chess programming - predictions for the next 5 years

Post by cdani » Sun Feb 03, 2019 10:30 pm

My attemps are mostly improving Andscacs positionally, without forgetting other more standard approaches. Not much success for the moment...

Robert Pope
Posts: 476
Joined: Sat Mar 25, 2006 7:27 pm

Re: chess programming - predictions for the next 5 years

Post by Robert Pope » Mon Feb 04, 2019 5:22 pm

I think there are still a lot of fundamental advances to be made on the search side, and that has been significantly sidelined while focus is currently put on the actual training side. AlphaZero/Lc0 node expansion techniques are still in their infancy, and there are so many possibilities to be explored, just as was done for AlphaBeta searchers over the past 30 years.

henk2
Posts: 30
Joined: Mon Jan 14, 2019 6:55 am
Full name: Henk Verbaasdonk

Re: chess programming - predictions for the next 5 years

Post by henk2 » Tue Feb 05, 2019 5:27 pm

I think if (when, looking at GPU development vs CPU development. And dev of Lc0 compared to sf) Leela starts beating SF with GPUs, the developers should start focusing on turning Lc0 into the strongest CPU engine too. So hardware is truly apples to apples.

Then maybe if people are willing to spend the resources we can get other NN-engines that use A/B, NN-engines that use other forms of Best-First Search than MCTS, NN-engines that use a combination of search methods, etc. .
Classical engines could start using genetic algorithms to determine changes and new versions.
KMCTS is promising too and maybe it will eventually turn out stronger than regular K, maybe this will spread to other engines. Maybe we'll get hybrid CPU/GPU engines too.

There's still a lot of room to expand.
So many possibilities as long as people are willing.

grahamj
Posts: 31
Joined: Thu Oct 11, 2018 12:26 pm
Full name: Graham Jones

Re: chess programming - predictions for the next 5 years

Post by grahamj » Tue Feb 05, 2019 7:23 pm

I had no interest in chess programming until I read the AlphaZero paper. I haven't played chess for decades, and never seriously. I worked in computer vision 1995-2007, and followed the machine learning field at that time. The last ten years I have been working in mathematical biology. 15 months ago, I had never heard of Stockfish. Over the past year I have been catching up with ML, following LC0, learning about chess engines and CUDA programming, and writing my own CUDA chess engine. I am therefore looking at this question from a different angle to most of you, perhaps all of you.

I was surprised that methods developed for image recognition worked so well for Go and chess, and I was surprised at how deep convolutional nets have become since I last paid them much attention. But not very surprised. On the whole Stockfish was more surprising to me, especially two things. One, the huge amount of pruning that it does apart from alpha-beta pruning. There is so much non-alpha-beta pruning I don't like to call it an 'AB' engine. Two, the way that Fishtest goes on and on adding more ELOs linearly with time. I still find this counter-intuitive, and would have expected a slowdown by now.

I can see connections between the AlphaZero technology and some real-world problems. (Eg, branching processes, hence tree structures, are everywhere in biology. Natural selection is nature's pruning algorithm.) Will work done on real-world problems feed back into chess? (BTW, I do not believe there were 'shady things' going at DeepMind. The obvious motivation for the paper is that technology for patents must be made public. I dislike software patents, but they are not dishonest. I don't like the hype, but sadly, hype has become part of scientific research by academics as well as big companies.)

One thing that strikes me is that current engines either have a very lightweight evaluation and huge search tree or the opposite, heavyweight evaluation with correspondingly much smaller search tree. There is very little in the middle. Why so few medium-weight evaluation with medium-sized search trees? Some possible explanations:

1. No-one knows how to handcraft a good medium-weight (or heavyweight) evaluation, and too few chess programmers know enough about ML to do it that way.

2. Medium-weight (or heavyweight) evaluation is only better than lightweight evaluation when the former uses a GPU and the latter does not, and too few chess programmers know how to write GPU code.

3. A good algorithm for medium-sized search trees is missing. It's natural to store the whole tree if you can (like PUCT), or to store a path from root to tip if you can't (like simple alpha-beta pruning). It's harder to see how to make good use of be able to store say 10% of the nodes.

Predictions, not all about chess:

In 5 years the strongest engines will use ML-based evaluation and move ordering. Handcrafted evaluations may be used alongside, but the ML-based evaluation and move ordering will be an essential part. (I regard the policy vector in AlphaZero as a heavyweight move ordering.)

In 5 years the strongest engines will use GPUs but I am not saying exactly how they will be used.

Issues 1 and 2 will go away. In 2023 (assuming talkchess exists) there will be lots of talk here about regularization, cross-validation, warp divergence, instruction latency, and the like.

I am less sure about 3 being a real problem in the first place, and if it is, it may not be solved in 5 years. I think there will be significant advances in search algorithms, both theoretical and practical, but maybe they won't be relevant to medium size trees. Nonetheless, I'll go ahead and predict the emergence of chess engines in the middle, as serious contenders.

Several companies will licence DeepMind's patent on AlphaZero technology for tackling real-world problems. This will not feed back into chess within 5 years, but maybe one day.

Interest in neural nets will wane, maybe not in 5 years, but within 10 years, ML researchers will have a new technology to get overexcited about.
Graham Jones, www.indriid.com

Dann Corbit
Posts: 9638
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: chess programming - predictions for the next 5 years

Post by Dann Corbit » Tue Feb 05, 2019 8:01 pm

We humans are really, really bad at predicting the future[*].
Mathematically, even if you have really good data, the projection of the error bars grows astonishingly fast when you go past either end of the data.
Therefore, I think the safest thing to say is, "We have no idea what trends are going to be successful in the future"

[*] Though science fiction writers have been surprisingly good at it. I attribute this success to two things:
First, they are projecting with intelligent research. Typically, they talk to current researchers so verify their postulates. (An example is Jules Vern's "From the Earth to the Moon" where he talked to scientists and mathematicians who told him [for instance] that a near-equatorial launch would be best because you will gain about 1000 MPH).
Second, the readers of science fiction are perhaps inspired to try the ideas that are given by the writers.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Dann Corbit
Posts: 9638
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: chess programming - predictions for the next 5 years

Post by Dann Corbit » Tue Feb 05, 2019 8:04 pm

I am surprised no one has mentioned quantum computing. One of the algorithms that can be applied to a quantum computer is search.
5 years from now, I think we will have practical quantum computers. Perhaps with as many as 64 qbits.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Post Reply