Author: Vincent Diepeveen
Date: 15:16:54 10/04/03
Go up one level in this thread
On October 04, 2003 at 14:54:39, Omid David Tabibi wrote:
>Going back to McAllester and Yuret's 1993 article, Alpha-Beta Conspiracy Search,
>the idea seems very interesting. Apparently this idea hasn't received much
>attention, and the only top engine which uses a conspiracy search is P.ConNerS.
>
>Has anyone tried the ABC algorithm? Any experimental results eversince the
>original publication in 1993?
I have spent months on a CNS version of diep. If memory serves me well that
happened start of 2001.
It was said by rumours that
a) it was tactical strong way to search
b) it's not depth limited
Further i need to mention that p.conners is using cns2 and not cns1.
After having put in a lot of time at it i figured out a number of problems with
it i need to notice a few things
a) diep with bruces SE hands down is tactical stronger at a PC than p.conners
at 200 processors is, despite that DIEP isn't created to just solve tactics
b) the difference between CNS1 and CNS2 is that Ulf with cns2 tried to find
proof for 2 leaves having the PV score. Yet the implementation of that must have
been done with bugs in P.Conners, i cannot conclude anything else than that.
c) much of the tactical strength of p.conners is based upon the fact that
every 'leaf' is in fact a 2 ply alfabeta search. If i allow the cns
implementation of diep to be having leafs of 2 ply it suddenly is a lot
stronger, whereas i didn't do that at all. I used CNS1 and used 1 ply searches.
not 2 ply.
d) nullmove is usable but assigning a proper CNS value to it is hard.
So i used 100 there.
I basically tried to find tactical tricks with it. Because if you can't find a 3
move combination then forget it.
CNS in my experiments could NOT find easily this 6 ply trick:
Larsen:
r4rk1/pp2ppbp/6p1/8/Qnq1P3/2N1BPPb/PP4NP/R4RK1 b - - bm Bxg2; id "GMG1.100";
h3g2
However it found amazingly quickly:
3r1rk1/1pq1nppp/p7/2pB3Q/P4P2/1P2P3/6PP/2RR2K1 w - - bm Rxc5; id "GMG1.092";
c1c5
If i use current diep versions to find both tricks, that's a diep version with
R=3/2 and only check extensions. So no recaptures which is very crucial because
cns doesn't do recapture extensions either. Of course i did force it to extend
checks.
[D]r4rk1/pp2ppbp/6p1/8/Qnq1P3/2N1BPPb/PP4NP/R4RK1 b - -
bm Bxg2; id "GMG1.100";
00:00 5 0k 0 0 5 (1) 1 (0,0) 1.039 Bg7xc3 b2xc3 Qc4xc3 Be3xa7
00:00 28 0k 0 0 28 (1) 1 (0,0) 1.119 Rf8-d8
00:00 150 0k 0 0 150 (1) 2 (0,1) 0.682 Rf8-d8 Nc3-d5
++ g7-c3 procnr=0 terug=1039 org=[682;683] newwindow=[682;520000]
00:00 239 0k 0 0 239 (1) 2 (0,1) 1.039 Bg7xc3 b2xc3 Qc4xc3 Be3xa7
00:00 66950 67k 0 0 1339 (1) 3 (0,2) 2.221 Bg7xc3 b2xc3 Qc4-e2
00:00 107966 108k 0 0 3239 (1) 4 (0,3) 0.866 Bg7xc3 b2xc3 Qc4xc3 Rf1-c1
00:00 88821 89k 0 0 24870 (1) 5 (0,4) 1.256 Bg7xc3 b2xc3 Qc4xc3 Rf1-b1 Qc3-c2
00:00 98324 98k 0 0 64894 (1) 6 (0,5) 1.658 Bg7xc3 b2xc3 Bh3xg2 c3xb4 Bg2xf1 R
a1xf1
++ h3-g2 procnr=0 terug=1667 org=[1658;1659] newwindow=[1658;520000]
00:01 100155 100k 0 0 117182 (1) 6 (0,5) 3.194 Bh3xg2 Rf1-f2 Bg2-h3 Nc3-d5 a7-a5
Nd5xe7 Kg8-h8
So current diep version without forward pruning turned on needs 117182 nodes to
find bxg2. With recapture extensions it goes faster of course
Second position:
[D]3r1rk1/1pq1nppp/p7/2pB3Q/P4P2/1P2P3/6PP/2RR2K1 w - -
bm Rxc5; id "GMG1.092";
++ d5-e4 procnr=0 terug=273 org=[252;253] newwindow=[252;520000]
00:00 109174 109k 0 0 58954 (1) 6 (0,5) 0.381 Bd5-e4 Rd8xd1 Rc1xd1 f7-f5 Be4-f3
b7-b6 Rd1-d2
00:00 119845 120k 0 0 92281 (1) 7 (0,6) 0.260 Bd5-e4 Rd8xd1 Rc1xd1 f7-f5 Be4-f3
b7-b6 Rd1-d2 g7-g6
++ d5-c4 procnr=0 terug=261 org=[260;261] newwindow=[260;520000]
00:01 112802 113k 0 0 161308 (1) 7 (0,6) 0.372 Bd5-c4 Rd8xd1 Rc1xd1 a6-a5 Qh5-g5
b7-b6 e3-e4 h7-h6
00:03 119302 119k 0 0 406823 (1) 8 (0,7) 0.348 Bd5-c4 g7-g6 Qh5-g5 Ne7-f5 e3-e4
Nf5-d4 e4-e5 b7-b6 Bc4xa6 Nd4xb3
++ d5-e4 procnr=0 terug=349 org=[348;349] newwindow=[348;520000]
00:04 119021 119k 0 0 495129 (1) 8 (0,7) 0.449 Bd5-e4 f7-f5 Rd1xd8 Qc7xd8 Be4xb7
Qd8-b6 Qh5-f3 Qb6xb3
00:07 121757 122k 0 0 942404 (1) 9 (0,8) 0.332 Bd5-e4 Rd8xd1 Qh5xd1 f7-f5 Be4-f3
a6-a5 Qd1-d3 b7-b6 Rc1-d1 Kg8-h8
++ d5-c4 procnr=0 terug=333 org=[332;333] newwindow=[332;520000]
00:11 121061 121k 0 0 1411575 (1) 9 (0,8) 0.410 Bd5-c4 g7-g6 Qh5-h3 Kg8-g7 Rd1xd
8 Rf8xd8 Qh3-f3 f7-f5 e3-e4
00:26 119683 120k 0 0 3117754 (1) 10 (0,9) 0.330 Bd5-c4 Ne7-g6 Rd1xd8 Rf8xd8 Bc4
-e2 Rd8-c8 b3-b4 Qc7-e7 Qh5-h3 Rc8-e8
++ c1-c5 procnr=0 terug=331 org=[330;331] newwindow=[330;520000]
00:37 120256 120k 0 0 4519254 (1) 10 (0,9) 0.847 Rc1xc5 Qc7-b6 Rc5-c3 Ne7xd5 Rd1
xd5 Rd8xd5 Qh5xd5 Rf8-d8 Qd5-h5 g7-g6
You see deeper tricks can be found pretty quick with extensions, that was the
main reason to experiment with it. Now of course you can find also Rxc5 quicker
by extending checks more then this is a 9 ply trick. In fact with SE diep finds
this at 7 ply or something.
Then Rxc5 is found nearly instantly.
However with CNS of course you are at new terrain just discovering how to do
things.
The first real big question when CNS works kind of is how to feed the search.
Remember i had everything stored in a hashtable. So the entire search was stored
with CNS numbers inside it.
Many complain about cns being memory limited. Though that's true, memory is
cheap. If your node count is low then you can put tens of millions of nodes into
a single tree in memory, no problems there.
When that was all bugfree working the next thing to investigate and this is a
real big problem was how to feed the search. Which branch do you pick?
I write this down several times here because it is crucial. I soon found out
that just feeding the lowest CNS number wasn't worth it.
It is not impossible for me to imagine that some day someone will come up with a
search idea similar to this which is automatically taking care for a better load
balancing.
But please remember that with alfabeta pruning, CNS will in the root have for
each move a score 1 for its conspiracy number.
So basically you keep researching the same move deeper and deeper and usually
this is a big nonsense move.
So the problem soon was identified that there was no load balanching in the
search or whatsoever.
Now we can look for artificial ways to improve upon that and p.conners did just
that with cns2.
However that is an artificial way to take care for things.
What we really want is a way to search deeper and where o where do we do that?
When you start dividing in a primitif way the nodes. Where each 'node' is a 1
ply search of course, then the problem is not solved but another problem
announces itself.
Each millisecond the main variation gets a new one.
Suppose there is 5 reasonable moves in this position. Then trivially if we
research the first move that will give us a new mainline.
Now again i just basically researched fail high positions as i call them.
positions with tricks. so score goes up and up there.
But if you search positions where score goes slightly down because your position
sucks, then the 'mainline' without hesitation will be a 4 ply mainline or
something. Because that position with the shortest lines searched and therefore
the most idiotic moves which allow nullmove, will get your new mainline then.
Imagine that you search millions of positions and you end up with a 4 ply
mainline.
This is pretty sick nah?
So Ulf adressed that in CNS2.
However if i rudely may express what p.conners did (did because i doubt we will
ever see it in action again) is defining a certain brute force search depth
until where each cns search is forced to search to.
So suppose we pick 6 ply.
So that's a fullwidth search of 8 ply of every line. Additionally each line in
p.conners is a 2 ply search which hides the problem a bit as you get 1 ply for
free extra. So that's directly 8 ply then.
Now we can see this as a program doing 8 plies fullwidth and then a few more
selective plies. Regrettably that effectively means that even when you search
100 billion nodes, that some search lines will be garantueed to be 10 ply.
That is a problem if the trick is hard to find.
But suppose you nullmove, get a big CNS number back, but *after* this nullmove
there is the trick.
CNS will forever miss that unless you FORCE it to search deeper.
But wasn't cns exactly supposed to be there to determine ITSELF what to search
deeper?
So if CNS isn't going to search the necessary search space why use CNS anyway?
CNS2 is just a hack IMHO to add a few brute force things to CNS.
The 2 values idea to verify that a position is good is of course going to fail,
basically p.conners could do this because of using a window where the search is.
so [A;B] where A = B - 0.25 pawns.
Even that won't work very well because using a transposition table with CNS is
anything but trivial.
Anyway it is interesting to toy with this until you realize what you were doing.
I definitely feel that Ulf did some very interesting investigations here.
However he should come up with search results and if those are not good then i
do not care. I just want to hear his viewpoint on researched ideas which did NOT
work. Because if you know what does NOT work then that is perhaps the most
important information you can get in todays game tree search; there is too many
algorithms to try out yourself.
It is this last thing where i was utterly dissappointed in. The few researchers
there were in this field, they write some unrecognizable nonsense. No doubt it
is 'well written', but it is complete nonsense from practical viewpoint and
especially from theoretical game tree search viewpoint.
Just show me the code of how the CNSII program looked like.
Then i can verify within 10 minutes what it didn't do compared to my experiments
and what it did do.
So my conclusion was that where CNS sounds very interesting, it doesn't solve
the basic problem and that's *what* to search.
I didn't even yet open the discussion of what does it search *then*.
It is very dependant upon how good your evaluation is. Small errors in
evaluation do NOT get corrected by CNS. In contradiction, it's only making it
worse. That what your evaluation is missing, even a small bug in it, will
mercilous beam down onto you and lose the game because of it.
So doing a fullwidth search at 200 processors with 2 ply leafs definitely looks
good in achievements perhaps, but it renders the entire CNSII name it carries to
the far past history.
If i do at 200 processors an experiment without regurarly writing online what my
results were, having full access to a supercomputer continuesly, then trivially
one should expect to see search lines posted to the internet.
That's what i will do with diep world championship 2003. All my logfiles will be
published and available for who wants to have them, *whatever* the results
there. So you can verify later my nodes a second, the tactical strength of the
version at depth D and so on.
From deep blue logfiles everything, like how many processors were put to busy,
how effective the processors were used. And most important: how many nodes were
searched. So not nodes like in our programs, but searchjobs to the processors.
How can someone say his program has speed X without providing the number of
nodes searched in mainlines?
Yet the logfiles of the games are there with moves and times needed.
It is very typical for all these researchers that they didn't do that at all.
P.conners, missing everything. I have seen it in action so i know how tactical
weak it was. It missed some pawn wins against diep. I remember failing low after
a very bad game in the endgame to -2.5 pawns. I simply lost a pawn. It missed
it. It was like a 12 ply line or so. Not so deep in endgame.
P.Conners after 2 minutes of search missed it simply. So far the strong tactics.
Now we could forgive it that. Remember it was a very experimental program, try
to make an experimental program yourself and beat very strong programs and human
players with it. That's *not* easy.
So Ulf definitely has the privilege of the doubt there.
It is just sad that so many things that do *not* work are not described by him
at papers. Most researchers might not understand how important for commercial
game tree programmers such conclusions are.
That's why i did the research myself, but as you see i will not tell you how
good diep CNS was.
It sucked ass.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.