Page 4 of 5

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

Posted: Mon Sep 20, 2010 3:22 pm
by Don
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.

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

Posted: Mon Sep 20, 2010 3:31 pm
by Jouni
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

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

Posted: Mon Sep 20, 2010 4:41 pm
by bob
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.

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

Posted: Mon Sep 20, 2010 4:44 pm
by bob
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...

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

Posted: Mon Sep 20, 2010 8:31 pm
by Uri Blass
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

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

Posted: Mon Sep 20, 2010 10:12 pm
by Don
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.

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

Posted: Mon Sep 20, 2010 11:14 pm
by Sean Evans
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!

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

Posted: Tue Sep 21, 2010 5:59 am
by Dr.Wael Deeb
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....

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

Posted: Wed Sep 22, 2010 4:13 am
by Nimzovik
(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: )

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

Posted: Wed Sep 22, 2010 5:39 am
by S.Taylor
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?