An alternative to IID

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
Rebel
Posts: 7207
Joined: Thu Aug 18, 2011 12:04 pm
Full name: Ed Schröder

An alternative to IID

Post by Rebel »

Took IID out (of my oldie) and replaced it with a full ply reduction without research and it gave me +17 elo after 5000 games.

Not sure if that works for modern searchers.
90% of coding is debugging, the other 10% is writing bugs.
Joost Buijs
Posts: 1597
Joined: Thu Jul 16, 2009 10:47 am
Location: Almere, The Netherlands

Re: An alternative to IID

Post by Joost Buijs »

Rebel wrote: Thu Aug 13, 2020 8:46 am Took IID out (of my oldie) and replaced it with a full ply reduction without research and it gave me +17 elo after 5000 games.

Not sure if that works for modern searchers.
Do you mean that you first call the search with depth-2 before you do the regular search with depth-1?

IID as a whole does little to nothing in my engine, I took it out a long time ago.
User avatar
Rebel
Posts: 7207
Joined: Thu Aug 18, 2011 12:04 pm
Full name: Ed Schröder

Re: An alternative to IID

Post by Rebel »

From the CPW:
Internal Iterative Deepening (IID),
used in nodes of the search tree in a iterative deepening depth-first alpha-beta framework, where a program has no best move available from a previous search PV or from the transposition table. IID is used to find a good move to search first by searching the current position to a reduced depth, and using the best move of that search as the first move at the real depth.

I changed the blue reducing the depth by one and skip the research.

It's a different way to handle unsorted trees.

As a result my oldie almost searches 2 plies deeper.

Code: Select all

Engine                 Depth       Time   Games     Moves  Average Forfeit  Book Depth     MIDG   EARLY    ENDG    LATE
220                    12.67   92:18:25    5000    348498    0.95     0    39719  7.94    11.34 | 12.04 | 12.68 | 15.90
240                    14.49   91:36:33    5000    348370    0.95     0    39727  7.95    13.14 | 13.84 | 14.51 | 17.75
90% of coding is debugging, the other 10% is writing bugs.
Joost Buijs
Posts: 1597
Joined: Thu Jul 16, 2009 10:47 am
Location: Almere, The Netherlands

Re: An alternative to IID

Post by Joost Buijs »

Rebel wrote: Thu Aug 13, 2020 9:18 am From the CPW:
Internal Iterative Deepening (IID),
used in nodes of the search tree in a iterative deepening depth-first alpha-beta framework, where a program has no best move available from a previous search PV or from the transposition table. IID is used to find a good move to search first by searching the current position to a reduced depth, and using the best move of that search as the first move at the real depth.

I changed the blue reducing the depth by one and skip the research.

It's a different way to handle unsorted trees.

As a result my oldie almost searches 2 plies deeper.

Code: Select all

Engine                 Depth       Time   Games     Moves  Average Forfeit  Book Depth     MIDG   EARLY    ENDG    LATE
220                    12.67   92:18:25    5000    348498    0.95     0    39719  7.94    11.34 | 12.04 | 12.68 | 15.90
240                    14.49   91:36:33    5000    348370    0.95     0    39727  7.95    13.14 | 13.84 | 14.51 | 17.75
Ah I see, it's not very different from what I used to do, I took it out because in my engine it doesn't do much and it only increases pressure on the transposition table.

Code: Select all

	TT.get(ss->pos, ply, &entry);

	// internal iterative deepening
	if (depth >= 5 && entry.move == 0)
	{
		search_pv(ss, alpha, beta, depth - 2, ply, tn);
		TT.get(ss->pos, ply, &entry);
	}
User avatar
silentshark
Posts: 327
Joined: Sat Mar 27, 2010 7:15 pm

Re: An alternative to IID

Post by silentshark »

Rebel wrote: Thu Aug 13, 2020 8:46 am Took IID out (of my oldie) and replaced it with a full ply reduction without research and it gave me +17 elo after 5000 games.

Not sure if that works for modern searchers.
Interesting idea. I will give this a go, as I've never been happy with my IID implementation anyway. Will post back results after a few thousand games.
User avatar
silentshark
Posts: 327
Joined: Sat Mar 27, 2010 7:15 pm

Re: An alternative to IID

Post by silentshark »

silentshark wrote: Thu Aug 13, 2020 6:05 pm
Rebel wrote: Thu Aug 13, 2020 8:46 am Took IID out (of my oldie) and replaced it with a full ply reduction without research and it gave me +17 elo after 5000 games.

Not sure if that works for modern searchers.
Interesting idea. I will give this a go, as I've never been happy with my IID implementation anyway. Will post back results after a few thousand games.
+13 ELO after 2.5K games for me.. looking interesting
Joost Buijs
Posts: 1597
Joined: Thu Jul 16, 2009 10:47 am
Location: Almere, The Netherlands

Re: An alternative to IID

Post by Joost Buijs »

Rebel wrote: Thu Aug 13, 2020 9:18 am From the CPW:
Internal Iterative Deepening (IID),
used in nodes of the search tree in a iterative deepening depth-first alpha-beta framework, where a program has no best move available from a previous search PV or from the transposition table. IID is used to find a good move to search first by searching the current position to a reduced depth, and using the best move of that search as the first move at the real depth.

I changed the blue reducing the depth by one and skip the research.
At first glance I didn't understood what you are doing, you just decrease the depth by 1 when there is no tt-move available, I never tried this, it looks interesting. I'm in the middle of a totally different project, when I have some time I will try this as well and let you know the result.
User avatar
silentshark
Posts: 327
Joined: Sat Mar 27, 2010 7:15 pm

Re: An alternative to IID

Post by silentshark »

silentshark wrote: Thu Aug 13, 2020 9:38 pm
silentshark wrote: Thu Aug 13, 2020 6:05 pm
Rebel wrote: Thu Aug 13, 2020 8:46 am Took IID out (of my oldie) and replaced it with a full ply reduction without research and it gave me +17 elo after 5000 games.

Not sure if that works for modern searchers.
Interesting idea. I will give this a go, as I've never been happy with my IID implementation anyway. Will post back results after a few thousand games.
+13 ELO after 2.5K games for me.. looking interesting
+14 ELO after 7.5K games for me now..

This does spark other ideas. I might try the following - tweaking LMR reduction, e.g reduce more if there is not a hash move

Anyhow, Ed's idea seems to have promise on its own. Overall depth increases quite a lot (like 1 or 2 plies), and strength increases slightly.
User avatar
Rebel
Posts: 7207
Joined: Thu Aug 18, 2011 12:04 pm
Full name: Ed Schröder

Re: An alternative to IID

Post by Rebel »

Internal Iterative Deepening (IID) becomes :

Internal Iterative Reductions (IIR)

or TTR

:D
90% of coding is debugging, the other 10% is writing bugs.
User avatar
silentshark
Posts: 327
Joined: Sat Mar 27, 2010 7:15 pm

Re: An alternative to IID

Post by silentshark »

Rebel wrote: Fri Aug 14, 2020 9:17 am Internal Iterative Deepening (IID) becomes :

Internal Iterative Reductions (IIR)

or TTR

:D
Nice! IIR, I like it.

I wonder what it would do in one of the super strong, 3000 ELO+ engines?