An alternative to IID

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Rebel
Posts: 5478
Joined: Thu Aug 18, 2011 10:04 am

An alternative to IID

Post by Rebel » Thu Aug 13, 2020 6: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.
90% of coding is debugging, the other 10% is writing bugs.

Joost Buijs
Posts: 1145
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: An alternative to IID

Post by Joost Buijs » Thu Aug 13, 2020 7:00 am

Rebel wrote:
Thu Aug 13, 2020 6: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: 5478
Joined: Thu Aug 18, 2011 10:04 am

Re: An alternative to IID

Post by Rebel » Thu Aug 13, 2020 7: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
90% of coding is debugging, the other 10% is writing bugs.

Joost Buijs
Posts: 1145
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: An alternative to IID

Post by Joost Buijs » Thu Aug 13, 2020 7:34 am

Rebel wrote:
Thu Aug 13, 2020 7: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: 283
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: An alternative to IID

Post by silentshark » Thu Aug 13, 2020 4:05 pm

Rebel wrote:
Thu Aug 13, 2020 6: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: 283
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: An alternative to IID

Post by silentshark » Thu Aug 13, 2020 7:38 pm

silentshark wrote:
Thu Aug 13, 2020 4:05 pm
Rebel wrote:
Thu Aug 13, 2020 6: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: 1145
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: An alternative to IID

Post by Joost Buijs » Fri Aug 14, 2020 5:13 am

Rebel wrote:
Thu Aug 13, 2020 7: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: 283
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: An alternative to IID

Post by silentshark » Fri Aug 14, 2020 6:43 am

silentshark wrote:
Thu Aug 13, 2020 7:38 pm
silentshark wrote:
Thu Aug 13, 2020 4:05 pm
Rebel wrote:
Thu Aug 13, 2020 6: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: 5478
Joined: Thu Aug 18, 2011 10:04 am

Re: An alternative to IID

Post by Rebel » Fri Aug 14, 2020 7:17 am

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: 283
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: An alternative to IID

Post by silentshark » Fri Aug 14, 2020 7:31 am

Rebel wrote:
Fri Aug 14, 2020 7: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?

Post Reply