Modified Scidlet (added IID)

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 24 July 2004 04:17:39:

Source, project, and binaries:
ftp://cap.connx.com/pub/chess-engines/n ... CIDLET.ZIP
Binary only:
ftp://cap.connx.com/pub/chess-engines/n ... cidlet.exe



my ftp site {remove http:// unless you like error messages}

[Norm Pollock]

Geschrieben von:/Posted by: Norm Pollock at 24 July 2004 04:28:52:
Als Antwort auf:/In reply to: Modified Scidlet (added IID) geschrieben von:/posted by: Dann Corbit at 24 July 2004 04:17:39:

Source, project, and binaries:
ftp://cap.connx.com/pub/chess-engines/n ... CIDLET.ZIP
Binary only:
ftp://cap.connx.com/pub/chess-engines/n ... cidlet.exe

What is IID?

[Uri Blass]

Geschrieben von:/Posted by: Uri Blass at 24 July 2004 04:35:50:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Norm Pollock at 24 July 2004 04:28:52:

Source, project, and binaries:
ftp://cap.connx.com/pub/chess-engines/n ... CIDLET.ZIP
Binary only:
ftp://cap.connx.com/pub/chess-engines/n ... cidlet.exe

What is IID?

Internal iterative deepening that is doing a search to reduced depth only for better order of moves in part of the nodes.
Something that movei of today also still does not have.
Uri

[Roy Harper]

Geschrieben von:/Posted by: Roy Harper at 24. July 2004 05:16:
Als Antwort auf:/In reply to: Modified Scidlet (added IID) geschrieben von:/posted by: Dann Corbit at 24 July 2004 04:17:39:

Regarding ftp://cap.connx.com/pub/chess-engines/new-approach
Please advise when this site comes back on line as I have tried several times for a week now and get nothing. Have tried Netscape and IE6 same results (other ftp sites) come on for me so is not my computer..

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 24 July 2004 06:45:01:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Norm Pollock at 24 July 2004 04:28:52:

Source, project, and binaries:
ftp://cap.connx.com/pub/chess-engines/n ... CIDLET.ZIP
Binary only:
ftp://cap.connx.com/pub/chess-engines/n ... cidlet.exe

What is IID?

Uri's description is correct. Here is a brief write-up by Colin Frayn:
http://www.chessbrain.net/beowulf/theory.html#iid
The nice thing about IID is that it is totally simple to install if your hash is working well.
The notion is this:
Move ordering in Alpha-Beta is all-important. The difference between worst possible choice and best possible choice for the node searched first is that the right choice will cause the square root of the number of nodes of the worst choice to be searched. And the best way to know what to search is to examine PV nodes first.
So what happens if you have no pv node? Just do a search of the current position at depth-2. That will be 1/4 of the effort or less of a full search (if you have an excellent branching factor of 2) and it will ensure that your move ordering is nearly optimal by creation of a pv node in your hash table. This also assumes that your eval function is decent. There are a few small tweaks to the idea to make it work. For instance, you only search at d-2 when d-2 >= 1.



my ftp site {remove http:// unless you like error messages}

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 24 July 2004 08:48:41:
Als Antwort auf:/In reply to: Modified Scidlet (added IID) geschrieben von:/posted by: Dann Corbit at 24 July 2004 04:17:39:

Source, project, and binaries:
ftp://cap.connx.com/pub/chess-engines/n ... CIDLET.ZIP
Binary only:
ftp://cap.connx.com/pub/chess-engines/n ... cidlet.exe

Improved condition for IID search, and also this one labels itself as "Scidlet 3.6.1 (IID)"



my ftp site {remove http:// unless you like error messages}

[Geoff]

Geschrieben von:/Posted by: Geoff at 24. July 2004 18:17:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Dann Corbit at 24 July 2004 06:45:01:

Hello Dan
Any chance you could post a position or two where there is a measureable speed up to depth x, with and without IID.
According to my understanding adding IID should just be something like the code below. I put this in my seach function just after getting a possible hash move, but before the Null move code.
/* IID experiment */
if ((depth >= 3) && (alpha != beta+1) && (hashMove.u == 0))
{
value = -search(-alpha-1, -alpha, (depth-2), doNull);
}

It not only didnt help my engine, it had a pretty severe adverse effect. No doubt I have probably got something wrong in my understanding of the idea, or the code inverted, backwards or upside down in someway
I did try tinkering with doNull ,making it fixed as TRUE or FALSE
also tinkered with the (alpha != beta+1) clause, no joy in any experiment
Regards Geoff

Source, project, and binaries:
ftp://cap.connx.com/pub/chess-engines/n ... CIDLET.ZIP
Binary only:
ftp://cap.connx.com/pub/chess-engines/n ... cidlet.exe

What is IID?

Uri's description is correct. Here is a brief write-up by Colin Frayn:
http://www.chessbrain.net/beowulf/theory.html#iid
The nice thing about IID is that it is totally simple to install if your hash is working well.
The notion is this:
Move ordering in Alpha-Beta is all-important. The difference between worst possible choice and best possible choice for the node searched first is that the right choice will cause the square root of the number of nodes of the worst choice to be searched. And the best way to know what to search is to examine PV nodes first.
So what happens if you have no pv node? Just do a search of the current position at depth-2. That will be 1/4 of the effort or less of a full search (if you have an excellent branching factor of 2) and it will ensure that your move ordering is nearly optimal by creation of a pv node in your hash table. This also assumes that your eval function is decent. There are a few small tweaks to the idea to make it work. For instance, you only search at d-2 when d-2 >= 1.

[Tim Mann]

Geschrieben von:/Posted by: Tim Mann at 26 July 2004 00:05:04:
Als Antwort auf:/In reply to: Modified Scidlet (added IID) geschrieben von:/posted by: Dann Corbit at 24 July 2004 04:17:39:

ftp://cap.connx.com

Mozilla always fails to access Dann's ftp site when I try it, so I took a few minutes to try to find out what's wrong.
I tried with a command-line ftp client and had more luck, after I guessed that one has to give username "anonymous" and an empty string as password. If you give an email address or some other arbitrary string as the password (as every other anonymous ftp site that I know about wants, or at least accepts), it fails. There's no hint in the prompt messages that an empty password must be used.
I'm not sure what Mozilla is giving for the password. I tried checking the box "Send this email address as anonymous FTP password" and leaving the field empty, but that didn't work. The syntax ftp://anonymous:@cap.connx.com didn't work either, surprisingly. Maybe there is a Mozilla bug compounding the problem.

[Andreas Herrmann]

Geschrieben von:/Posted by: Andreas Herrmann at 27 July 2004 18:06:22:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Geoff at 24. July 2004 18:17:

Hello Dan
Any chance you could post a position or two where there is a measureable speed up to depth x, with and without IID.
According to my understanding adding IID should just be something like the code below. I put this in my seach function just after getting a possible hash move, but before the Null move code.
/* IID experiment */
if ((depth >= 3) && (alpha != beta+1) && (hashMove.u == 0))
{
value = -search(-alpha-1, -alpha, (depth-2), doNull);
}

Hi Geoff,
i have implemented IID in my engine similiar to Crafty. You should have a look in the source of Crafty, to see what's diffrent with your code, especially your second condition, which should be the condition to compare if the current node is a pv node. I use also the additional condition: IsNullmoveAllowed. After the IID search i check also for a FailLow, and research in this case. And don't forget to get the new hash move after the IID search, if there is now one (should be in the most cases), to try this move first.
But don't expect a big speedup. In my engine BlackBishop it was in games with a 128 MB hash table only about 10 ELO better.
If you have already a good moveordering (bf

[Fabien Letouzey]

Geschrieben von:/Posted by: Fabien Letouzey at 27 July 2004 18:13:05:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Geoff at 24. July 2004 18:17:

I did try tinkering with doNull ,making it fixed as TRUE or FALSE
also tinkered with the (alpha != beta+1) clause, no joy in any experiment
Regards Geoff

I wasn't paying attention. "alpha != beta+1" should of course be replaced with "beta != alpha+1".
IID activates rarely when restricted to PV nodes. It might require several test positions before you even notice a difference (as compared with non-IID)!
Fabien.

[Uri Blass]

Geschrieben von:/Posted by: Uri Blass at 27 July 2004 19:11:07:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Andreas Herrmann at 27 July 2004 18:06:22:

Hello Dan
Any chance you could post a position or two where there is a measureable speed up to depth x, with and without IID.
According to my understanding adding IID should just be something like the code below. I put this in my seach function just after getting a possible hash move, but before the Null move code.
/* IID experiment */
if ((depth >= 3) && (alpha != beta+1) && (hashMove.u == 0))
{
value = -search(-alpha-1, -alpha, (depth-2), doNull);
}

Hi Geoff,
i have implemented IID in my engine similiar to Crafty. You should have a look in the source of Crafty, to see what's diffrent with your code, especially your second condition, which should be the condition to compare if the current node is a pv node. I use also the additional condition: IsNullmoveAllowed. After the IID search i check also for a FailLow, and research in this case. And don't forget to get the new hash move after the IID search, if there is now one (should be in the most cases), to try this move first.
But don't expect a big speedup. In my engine BlackBishop it was in games with a 128 MB hash table only about 10 ELO better.
If you have already a good moveordering (bf Or if you are using a big hash table, or a hash table with more than one >slot, it brings also not much, because you have in the most cases a best move >from the hash table.

I think that people confuse between a move that is good enough to fail high and a best move.
The things are not the same and a move that is good enough to fail high only needs to give a score that is bigger or equal to beta and does not need to give score that is bigger than other moves that are practically not searched.
move that gives the highest score at specific depth is also not always best move but at least you can consider it as best based on computer search when moves in the hash are not considered as best based on computer search but only as good enough.
Uri

[Pallav Nawani]

Geschrieben von:/Posted by: Pallav Nawani at 27 July 2004 20:19:25:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Roy Harper at 24. July 2004 05:16:

Regarding ftp://cap.connx.com/pub/chess-engines/new-approach
Please advise when this site comes back on line as I have tried several times for a week now and get nothing. Have tried Netscape and IE6 same results (other ftp sites) come on for me so is not my computer..

Hi,
try using an FTP client such as LeechFTP. You will have better results.
Pallav


Natwarlal

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 28 July 2004 02:27:16:
Als Antwort auf:/In reply to: Re: Modified Scidlet (added IID) geschrieben von:/posted by: Geoff at 24. July 2004 18:17:

Hello Dan
Any chance you could post a position or two where there is a measureable speed up to depth x, with and without IID.
According to my understanding adding IID should just be something like the code below. I put this in my seach function just after getting a possible hash move, but before the Null move code.
/* IID experiment */
if ((depth >= 3) && (alpha != beta+1) && (hashMove.u == 0))
{
value = -search(-alpha-1, -alpha, (depth-2), doNull);
}

It not only didnt help my engine, it had a pretty severe adverse effect. No doubt I have probably got something wrong in my understanding of the idea, or the code inverted, backwards or upside down in someway
I did try tinkering with doNull ,making it fixed as TRUE or FALSE
also tinkered with the (alpha != beta+1) clause, no joy in any experiment

I think a zero width search is a waste of time. In fact, Colin's method has a research in it:

/* ----------==== INTERNAL ITERATIVE DEEPENING ====----------- */

/* If we're not doing a NULL move and we don't have a hash move and we're at least 3
* ply away from the quiescence search, then try to get a good guess for the best move
* by doing a shallower search from here. */
if (USE_IID && hashmove==NO_MOVE && NullDepth==0 && depth >= THREEPLY && Skill>8 && !bRushed) {
score = Search(B,talpha,tbeta,depth - TWOPLY,ply,inchk,0,0,LastMove);
/* Re-search properly if the previous search failed low, so that we know we're getting
* a good move, not just the move with the highest upper bound (which is essentially
* random and depends on the search order.) */
if (score