Have we hit a wall on chess software after Rybka 4 came out?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Don » Mon Sep 20, 2010 1:22 pm

Graham Banks wrote:The horizon effect is still a problem, but I guess it will remain so for a long time to come.
Therefore, further development of long term planning could be a goal?
I'm not a programmer though.
I'm not sure this can be addressed directly - other than just continuing to look for ways to search deeper.

The fundamental nature of search causes this and it's the whole reason why we try to look deeper and deeper. So over time the "problem" gets smaller and smaller and the programs get stronger and stronger.

By the way the "horizon effect" is not the real problem, it's the limited horizon that is. If you are losing a piece and throw away a pawn to delay it, it doesn't change the fact that you were losing the game anyway. So the primary difficulty is that are not looking deeply enough period. HOWEVER, as long as you are not looking deep, you are going to see horizon effects.

Jouni
Posts: 2030
Joined: Wed Mar 08, 2006 7:15 pm

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Jouni » Mon Sep 20, 2010 1:31 pm

I am not so sure about Rybka tactics, from old WM test tactics :) :

Code: Select all

spark-0.4-256MB	Houdini 1.03a x64 2_CPU-256MB	Rybka 3 -256MB	Deep Rybka 4 x64-256MB	Stockfish 1.8 JA 64bit-256MB	
Alega - Aljechin	0:00:00	0:00:00	0:00:01	0:00:01	0:00:00	
Smyslov - Kotov	0:00:18	0:00:16	0:00:14	0:00:07	0:00:01	
Muchin - Tal	0:00:19	0:00:54	0:00:25	0:00:45	0:03:00	
Tal - Ftacnik	0:00:03	0:00:01	0:00:02	0:00:58	0:00:04	
Spassky - Geller	0:00:03	0:00:01	0:00:02	0:00:06	0:00:43	
Spassky - Bronstein	0:00:09	0:00:01	0:00:05	0:03:00	0:00:45	
Spassky - Unzicker	0:00:10	0:00:39	0:03:00	0:03:00	0:03:00	
Fischer - Benko	0:00:12	0:01:25	0:00:29	0:02:20	0:03:00	
Fischer - Stein	0:00:02	0:00:01	0:00:03	0:00:02	0:00:21	
Timman - Karpov	0:00:00	0:00:01	0:00:01	0:00:02	0:00:17	
Piket - Kasparov	0:00:07	0:00:01	0:00:02	0:00:02	0:00:04	
Aljechin - Fahrni	0:00:14	0:00:12	0:00:36	0:01:15	0:00:01	
Kudrin - Tal	0:00:01	0:00:01	0:00:01	0:00:01	0:03:00	
Kasparov - Short	0:00:00	0:00:00	0:00:01	0:00:02	0:00:02	
Aljechin - Rabinowitsch	0:00:00	0:00:00	0:00:01	0:00:01	0:00:00	
Anand - Bologan	0:00:07	0:00:12	0:00:36	0:03:00	0:03:00	
Kramnik - Beljavsky	0:00:00	0:00:01	0:00:01	0:00:01	0:00:01	
Fischer - Larsen	0:00:00	0:00:00	0:00:00	0:00:00	0:00:04	
Fischer - Ault	0:00:00	0:00:16	0:00:01	0:00:01	0:00:01	
Anand - Lautier	0:00:06	0:00:01	0:00:01	0:00:01	0:00:41	
Kasparov - Movsesian	0:00:18	0:00:17	0:00:13	0:00:37	0:00:18	
Tal - Letelier	0:01:15	0:00:29	0:00:11	0:00:45	0:00:01	
Fischer - Reshevsky	0:00:01	0:00:00	0:00:01	0:00:00	0:00:01	
Karpov - Kortschnoj	0:00:41	0:00:55	0:02:14	0:03:00	0:03:00	
Total time: 	0:04:08	0:05:45	0:08:21	0:19:07	0:21:27	
Total solved: 	24	24	23	20	18	

Jouni

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Have we hit a wall on chess software after Rybka 4 came

Post by bob » Mon Sep 20, 2010 2:41 pm

Graham Banks wrote:
bob wrote:
Alexander Schmidt wrote:
bob wrote:For the record, the horizon-effect will not go away until a program can see to the end of the game.
Of course there is always a horizon for the programms, but when we are talking about bad moves due to horizon effects, we talk about unforced material loses.
A horizon effect can and will cause problems at the root, otherwise it is not an issue. It is being used to push some consequence over the horizon so that the effect is hidden. The farther this occurs from the root, the greater the probability that you can change your mind before entering such a forced sequence of moves not knowing about the eventual bad outcome. But no matter what, this influences the score at the root, because you play a root move assuming that the path to the terminal node you like is optimal for both sides. If you suddenly find your key move can't be played, farther down in the game, then you are going to be forced away from the original score you were playing toward and have to accept something worse. How much worse? Impossible to say, obviously. But it could lead to material loss. Or just a positional bust that still causes you to lose the game later.
Bob - would you regard the following as an example of the horizon effect at play?

[Event "World Regional Teams Championship 2010"]
[Site "Auckland"]
[Date "2010.09.20"]
[Round "4.17"]
[White "spark-0.4"]
[Black "Chronos 1.9.9"]
[Result "1-0"]
[ECO "E55"]
[Annotator "0.60;0.15"]
[PlyCount "51"]
[EventDate "2010.09.10"]
[EventType "tourn"]
[Source "Banks"]
[TimeControl "40/1500:40/1500:40/1500"]

{Intel(R) Core(TM) i5 CPU 750 @ 2.67GHz 0 MHz W=19.6 ply; 1,893kN/s;
HS-Masterbook 2.0.ctg B=17.8 ply; 702kN/s; HS-Masterbook 2.0.ctg} 1. d4 {
[%eval 35534,0] [%emt 0:00:00]} Nf6 {[%eval 35534,0] [%emt 0:00:00]} 2. c4 {
[%eval 35534,0] [%emt 0:00:00]} e6 {[%eval 35534,0] [%emt 0:00:00]} 3. Nc3 {
[%eval 35534,0] [%emt 0:00:00]} Bb4 {[%eval 35534,0] [%emt 0:00:00]} 4. e3 {
[%eval 35534,0] [%emt 0:00:00]} c5 {[%eval 35534,0] [%emt 0:00:00]} 5. Bd3 {
[%eval 35534,0] [%emt 0:00:00]} O-O {[%eval 35534,0] [%emt 0:00:00]} 6. Nf3 {
[%eval 35534,0] [%emt 0:00:00]} d5 {[%eval 35534,0] [%emt 0:00:00]} 7. O-O {
[%eval 35534,0] [%emt 0:00:00]} dxc4 {[%eval 35534,0] [%emt 0:00:00]} 8. Bxc4 {
[%eval 35534,0] [%emt 0:00:00]} Nbd7 {[%eval 35534,0] [%emt 0:00:00]} 9. Qe2 {
[%eval 35534,0] [%emt 0:00:00]} b6 {[%eval 35534,0] [%emt 0:00:00]} 10. Rd1 {
[%eval 35534,0] [%emt 0:00:00]} cxd4 {[%eval 35534,0] [%emt 0:00:00]} 11. exd4
{[%eval 35534,0] [%emt 0:00:00]} Bb7 {[%eval 35534,0] [%emt 0:00:00]} 12. d5 {
[%eval 35534,0] [%emt 0:00:00]} Bxc3 {[%eval 15,16] [%emt 0:00:50]} 13. dxe6 {
[%eval 60,18] [%emt 0:00:43]} Bxf3 {[%eval 2,16] [%emt 0:00:50]} 14. gxf3 {
[%eval 54,19] [%emt 0:01:16]} fxe6 {[%eval 16,17] [%emt 0:00:50]} 15. Bxe6+ {
(bxc3) [%eval 49,18] [%emt 0:01:21]} Kh8 {[%eval 2,17] [%emt 0:00:50]} 16. bxc3
{[%eval 40,19] [%emt 0:01:36]} Re8 {(Qe8) [%eval -1,16] [%emt 0:00:50]} 17. Rd3
{(Ba3) [%eval 41,19] [%emt 0:00:55]} Nh5 {(Qc7) [%eval 14,17] [%emt 0:00:50]}
18. Qe4 {[%eval 58,20] [%emt 0:01:01]} Nhf6 {(Qf6) [%eval 26,18] [%emt 0:00:50]
} 19. Qf5 {[%eval 0,21] [%emt 0:01:30]} Qe7 {[%eval 39,17] [%emt 0:00:50]} 20.
Bxd7 {(Re3) [%eval 444,18] [%emt 0:00:44]} Qe1+ {[%eval 260,16] [%emt 0:03:20]}
21. Kg2 {[%eval 339,2] [%emt 0:00:00]} Re5 {(Re2) [%eval 402,15] [%emt 0:00:43]
} 22. Bd2 {(Be3) [%eval 570,19] [%emt 0:00:35]} Qe2 {
[%eval 445,18] [%emt 0:00:53]} 23. Re1 {[%eval 609,22] [%emt 0:01:05]} Qxe1 {
(Rxf5) [%eval 467,18] [%emt 0:00:42]} 24. Bxe1 {[%eval 635,22] [%emt 0:00:42]}
Rxf5 {[%eval 488,19] [%emt 0:00:42]} 25. Bxf5 {[%eval 645,23] [%emt 0:00:59]}
Re8 {(g6) [%eval 490,18] [%emt 0:00:42]} 26. Re3 {[%eval 672,22] [%emt 0:01:01]
} 1-0
I don't see anything using Crafty to analyze. Generally one tries some oddball move that does nothing more than delay the "problem" long enough that the search can't see it. Crafty spotted all the stuff with the pin of the black knight pretty quickly, so it never thought there was any way out. When Black played 19. Qe7 things were over. If there is an horizon effect, it might be right there. Crafty thinks Qe7 is something like +4.5, and suggests Rxe6 is a "less worse" alternative, being only +2.3... That is an indication of a possible horizon effect, since the score drops (for the side on move) significantly with a deeper search. Shallow searches suggest Qe7 is only slightly worse, something like +.3 or so...

Without seeing the actual engine output (I can't make heads or tails of the evals embedded in the PGN) it is hard to say, but it is possible.

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Have we hit a wall on chess software after Rybka 4 came

Post by bob » Mon Sep 20, 2010 2:44 pm

Don wrote:
Graham Banks wrote:
Alexander Schmidt wrote: Horizon effect is for example if a computer gives away a pawn for nothing to move a forced piece loss behind the search horizon. Modern programs usually are able to see this with their large extensions
In 99% of cases yes, but there are still occasions where the horizon effect occurs.
There are a LOT of occasions. They are just hidden from our view because we see them as positional moves so they go completely unnoticed. They probably occur in almost every games.
I agree. When the program's "horizon" is _way_ beyond our "horizon" we are not going to see 'em. We saw 'em repeatedly in the 70's and 80's, were a program would give up a pawn, to avoid losing a piece. And repeat several times, before finally giving up the piece anyway.

The only way we would have no horizon effect today would be if we had _perfect_ extensions and _perfect_ reductions. We don't... And we won't... Until we see to the end of the game...

Uri Blass
Posts: 8611
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Uri Blass » Mon Sep 20, 2010 6:31 pm

Don wrote:
Graham Banks wrote:The horizon effect is still a problem, but I guess it will remain so for a long time to come.
Therefore, further development of long term planning could be a goal?
I'm not a programmer though.
I'm not sure this can be addressed directly - other than just continuing to look for ways to search deeper.

The fundamental nature of search causes this and it's the whole reason why we try to look deeper and deeper. So over time the "problem" gets smaller and smaller and the programs get stronger and stronger.

By the way the "horizon effect" is not the real problem, it's the limited horizon that is. If you are losing a piece and throw away a pawn to delay it, it doesn't change the fact that you were losing the game anyway. So the primary difficulty is that are not looking deeply enough period. HOWEVER, as long as you are not looking deep, you are going to see horizon effects.
The horizon effect is a problem.

If you are losing 0.5 pawn and throw away 0.4 pawn to delay it, it clearly can change the result of the game because it is possible that
you can still draw when you are 0.5 pawns down but you cannot draw when you are 0.9 pawns down.

Uri

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Don » Mon Sep 20, 2010 8:12 pm

Uri Blass wrote:
Don wrote:
Graham Banks wrote:The horizon effect is still a problem, but I guess it will remain so for a long time to come.
Therefore, further development of long term planning could be a goal?
I'm not a programmer though.
I'm not sure this can be addressed directly - other than just continuing to look for ways to search deeper.

The fundamental nature of search causes this and it's the whole reason why we try to look deeper and deeper. So over time the "problem" gets smaller and smaller and the programs get stronger and stronger.

By the way the "horizon effect" is not the real problem, it's the limited horizon that is. If you are losing a piece and throw away a pawn to delay it, it doesn't change the fact that you were losing the game anyway. So the primary difficulty is that are not looking deeply enough period. HOWEVER, as long as you are not looking deep, you are going to see horizon effects.
The horizon effect is a problem.

If you are losing 0.5 pawn and throw away 0.4 pawn to delay it, it clearly can change the result of the game because it is possible that
you can still draw when you are 0.5 pawns down but you cannot draw when you are 0.9 pawns down.

Uri
Yes, of course. But what I'm saying is that this is just a subset of the bigger more relevant problem. The horizon effect is a special case of the general problem of limited horizon.

An example of the general problem is that you have a winning ending, 1 pawn up but you trade down to a minor piece vs king (no pawns.) This can be solved with better evaluation of course, but it illustrates the horizon problem. It's better to be 1 pawn up and winning that a piece up but drawing. It would take a really deep search to see that this is a draw.

Positions where there may or may not be compensation for a pawn or other sacrifice is another example. If your evaluation is wrong you depend on search which has a fairly limited horizon.

Sean Evans
Posts: 1777
Joined: Thu Jun 05, 2008 8:58 pm
Location: Canada

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Sean Evans » Mon Sep 20, 2010 9:14 pm

bob wrote:The only "wall" we have hit is that "some" can't break past the program they have copied. Others, with originality, will eventually catch and pass this "barrier" since they are not just copying what someone else wrote, but are actually writing their own...
Correct!

User avatar
Dr.Wael Deeb
Posts: 9635
Joined: Wed Mar 08, 2006 7:44 pm
Location: Amman,Jordan

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Dr.Wael Deeb » Tue Sep 21, 2010 3:59 am

Sean Evans wrote:
bob wrote:The only "wall" we have hit is that "some" can't break past the program they have copied. Others, with originality, will eventually catch and pass this "barrier" since they are not just copying what someone else wrote, but are actually writing their own...
Correct!
Correct and beautiful....
_No one can hit as hard as life.But it ain’t about how hard you can hit.It’s about how hard you can get hit and keep moving forward.How much you can take and keep moving forward….

Nimzovik
Posts: 1831
Joined: Sat Jan 06, 2007 10:08 pm

Re: Have we hit a wall on chess software after Rybka 4 came

Post by Nimzovik » Wed Sep 22, 2010 2:13 am

(Horizon effect may or may not affect what I am saying in this post. Smarter people that me can answer that question) I did not read this entire thread so I apologize in advance if I am displaying my ignorance. However my 2 bits is this... Did not Robert Hyatt a long time ago address the issue of engines having to address virtually a new Paradigm in terms of dealing with "Pablo Chess" and other positional considerations as opposed to the 'tactical' Holy Grail? Perhaps I am hallucinating but I would definitely like to re - read that post and save it in "My Documents" to quote for future reference. (Dang this wine is good :wink: )

S.Taylor
Posts: 8372
Joined: Thu Mar 09, 2006 2:25 am
Location: Jerusalem Israel

Re: Have we hit a wall on chess software after Rybka 4 came

Post by S.Taylor » Wed Sep 22, 2010 3:39 am

Dr.Wael Deeb wrote:
Sean Evans wrote:
bob wrote:The only "wall" we have hit is that "some" can't break past the program they have copied. Others, with originality, will eventually catch and pass this "barrier" since they are not just copying what someone else wrote, but are actually writing their own...
Correct!
Correct and beautiful....
Well? how far forward have we got?
Quite some secret eh?

Post Reply