Search Algorithm

[BertTuyt]

I have worked on LMR the last week.
In line with the Stockfish implementation (and suggested by Rein), I now have the next formula for the LMR depth-reduction:

Code: Select all

void CSearch64::DepthReduction_Init(void)
{
	int i, j, iReduction;
	double dReduction;


	for (i = 1; i < 64; i++)
	for (j = 1; j < 64; j++) {

		dReduction = 0.5 + log(double(i)) * log(double(j))/fLMR;

		iReduction = int(dReduction >= 1.0 ? floor(dReduction) : 0);

		iDepthReduction[i][j] = iReduction;
	}
}

And the inline function:

Code: Select all

inline int DepthReduction(int iDepth, int iMove) {

	return ( iDepthReduction[min(iDepth,63)][min(iMove,63)] );
}

I executed many 158-matches with different fLMR, and with 1 min search time for both engines (opponent as usual KingsRow).

I still used a limit for depth and movecount, whereas with the log*log approach I might omit this in a next test:

Code: Select all

			if (pSearchThreadData->bLMR && (pTDepth->bPV == false) && (pTDepth->iXCapture == 0) && (iXMovesSearched >= 4) && (iNewDepth >= 3)) {

				iRDepth = (bDDepth && pTDepth->bPromotion == false ? iNewDepth - 1 : iNewDepth) - DepthReduction(iNewDepth, iXMovesSearched);
				iRDepth = max(iRDepth, 1);

				iMWScore = -SearchX(iSearchThreadID, iRDepth, -iAlfa-1, -iAlfa, pTDepth + 1, pEngineData, !bTurn);

The results prove once again that you need to run many games to get some statistics, and that for a better understanding 3-move ballots is the minimum (as 158 is not sufficient with these differences).
In the Table the ELO-difference as a function of fLMR (Perspective Damage).

Code: Select all

     LMR Off   LMR On
0.5	-2	    -42
1	  -2	     0
2	  -2	     2
3	  -2	    -11
4	  -2	     18
5	  -2	     2
6	  -2	    -11
7	  -2	    -2
8	  -2	    -31
9	  -2	    -29

And all the Match Results (Perspective KingsRow):

Code: Select all

fLMR 0.5	1	  2	  3	  4	   5	  6	 7	  8	  9	  off
W	 25	 15	 17	 12	 10	 12	 17	 16	 25	 26	 14
L	 6	  15	 18	 7	  18	 13    12	 15	 11	 13	 13
D	 127	128	123	139	130	133	129	127	122	119	131

Based on these results I might use fLMR = 4.0

Bert

[BertTuyt]

Herewith the Match Results File with fMLR = 4.0
I have all .pdn files from all Matches, but Im not sure some-one would be interested in them....

Bert

[Rein Halbersma]

Herewith the Match Results File with fMLR = 4.0
I have all .pdn files from all Matches, but Im not sure some-one would be interested in them....

Bert

Hi Bert,

Interesting results! You would still need many more games to be able to conclude anything. I would suggest running at least 4,000 games for each level of fLMR. IIRC, the Stockfish team uses ultra-blitz timing levels of a 5 seconds per game, so that you can test thousands of games per day.

Rein

[BertTuyt]

Hi Bert,

Interesting results! You would still need many more games to be able to conclude anything. I would suggest running at least 4,000 games for each level of fLMR. IIRC, the Stockfish team uses ultra-blitz timing levels of a 5 seconds per game, so that you can test thousands of games per day.

Rein

Rein, that was also my remark. At least I believe that the tails seems okish, which means there LMR does not work.
But the optimum is a different story...
I need to rethink how to modify my program so I can play zillions of game during a day.
Also the number of messages will explode so communication does not work anymore.
Do you have some insights if the Stokfish teams modified the program in a specific way to enable this huge number of games??

Bert

[MichelG]

It takes some effort and compromises to make your engine play faster games, but i can tell you it is worth it.

I do most tests in dragon by self-play, with 2 versions of the program running in the same executable. That way you can avoid the communication time. In many cases, i can test under single-core circumstances, allowing many engines to run simultaneous. At fixed 6 ply search depth, this is giving me 25000+ test-games per hour.

For other test, a fixed time per game is required. But even at 10 sec/game this still gives 2000 games per hour.

For playing against other engines with damexchange, you have the problem of a minimum game time of 1/minute, making it very hard to get any meaningful result

Michel

[Krzysztof Grzelak]

Herewith the link for the Horizon 4.1 download.
The program runs only a 64bit Windows OS, and uses some new intrinsics (so on older processor this might not work)
Also 8 Gbyte memory (or more ) is recommended (as the default size for the DB is 4 GByte).

https://www.dropbox.com/sh/p9e998wvzgb4ipp/mpbgrowM9m

You can run this Engine in a standalone way, or add this application to the engines directory of the Damage GUI.

The engine runs normally on 1 core.
I did not modify the engine options to change the number of cores.

If you want to run Horizon on 4 cores, just type:
$ppproc 4
$ppmode 3

If you want to start a DXP match (example use Horizon in initiator mode):

levelsfixedtime 15 ( for a 10 min/game setting, use 15 sec/move)
opponents engine-engine
$ppproc 4
$ppmode 3
$dxp client
$dxp match
$dxp go

Just let me know when something does not work...

Bert

Hi Bert.

Bert that's all is acting correctly. Please how you can write it which to write the command so that the following time for the party plays the program - for example:

5 minutes for 75 moves
1 minutes for 100 moves.

I here still have one question. I noticed that during the match DXP at Core 1 a green lamp is keen and there is a yellow lamp switched on at Core 2 and Core 3. Whether you can write what it is determining.

[BertTuyt]

Hi Bert.

Bert that's all is acting correctly. Please how you can write it which to write the command so that the following time for the party plays the program - for example:

5 minutes for 75 moves
1 minutes for 100 moves.

I here still have one question. I noticed that during the match DXP at Core 1 a green lamp is keen and there is a yellow lamp switched on at Core 2 and Core 3. Whether you can write what it is determining.

The Timecontrol for the engine can be set with levelsfixedtime X (and X is the number of search-time in seconds).
I have not fully implemented (yet) in the engine a timecontrol for X Moves in Y Time.

However, for a DXP match I can communicate to the other program the number of moves and the total time.
Although my engine does not use the settings, it is practical when I want to run a match on different computers with different speed.
In this way I can set independently the search time for both.

The commands are:
$dxp prm m X (to set the number of moves for every DXP game to X ), example $dxp prm m 65
$dxp prm t Y (to set the time in minutes for 1 DXP Game), example $dxp prm 1

So to execute a DXP match with 158 games and 65 moves in 1 minute (for the opponent!) the next commands should be entered.

$dxp client
$dxp match
$dxp prm t 1
$dxp prm m 65
$dxp go

I use the LED's above the Core windows for debugging parallel-search purposes only (never tested this on super detail level, so it might go wrong sometimes).
The color explanation:
RED: Core not available so in case of a 1-core system (but with 2 hyperthreads) the Core-2 and Core-3 LED's are RED.
YELLOW: Core available but deactivated, to test systems with less cores, or to test scalability of the parallel search.
The number of cores active can be set with $ppproc X (example $ppproc 4).
BLUE: Core available, but search process not active. (example, all LED are BLUE after start-up). I sued it to check the behavior of the parallel-search (YBWC) process.
GREEN: Core available and search process active.

Hope this helps,

Bert

[Krzysztof Grzelak]

It thanks Bert. I have question what two options $ppproc 4 and $ppmode 3. How to put these options having processor i3 350 M.

[BertTuyt]

It thanks Bert. I have question what two options $ppproc 4 and $ppmode 3. How to put these options having processor i3 350 M.

I guess that the i3 350M is a dual-core processor with multithreading.
Therefore the program will "see" 4 cores.

With $ppmode you can set several search-modes, and switch between single-core search and multiple-core search (YBWC) and some test search options which I implemented for debugging purposes.
As, however, the parallel search is not fully implemented and tested in Horizon (later stage) , basically you don't need to use $ppproc and $ppmode, as the program will always run a single-core (traditional) search.

Bert

[Krzysztof Grzelak]

It thanks Bert. I have question what two options $ppproc 4 and $ppmode 3. How to put these options having processor i3 350 M.

I guess that the i3 350M is a dual-core processor with multithreading.
Therefore the program will "see" 4 cores.

With $ppmode you can set several search-modes, and switch between single-core search and multiple-core search (YBWC) and some test search options which I implemented for debugging purposes.
As, however, the parallel search is not fully implemented and tested in Horizon (later stage) , basically you don't need to use $ppproc and $ppmode, as the program will always run a single-core (traditional) search.

Bert

It thanks Bert.

[BertTuyt]

I have played another DXP match ( 1 min for every game) with the most recent Damage Engine (Version 12.4) against Kingsrow.
Normally these DXP games are directly played between the Engine and Kingsrow (as the Damage & Horizon Engine have DXP capabilities).
This time the DXP-connection was made via the Damage GUI (so far DXP was not yet implemented in the GUI).

The Damage Engine was connected via a GUIDE connection and Kingsrow via a DXP connection.
The DXP implementation in the Damage GUI is still embryonic as it is only possible to make a connection (from the perspective of the GUI).
Nevertheless most things seems to work.

Unfortunately it is so far not possible to play a DXP Match against Dragon, maybe related to the fact that the time between the acknowledge and the book move is too short.
Even with the additional delay ( a new option in Dragon) it does not work (yet).
So I need to dig somewhat deeper in the internals.

As I already implemented in the Damage GUI the structures and architecture for multiple Engines connected via multiple DXP-connections, it might be feasible in the feature to use the GUI as a Tournament Manager (but that's for later).

I will test also if I encounter problems with DAM 2.x and with the Truus and FLits DXP_server to make sure my implementation is more robust.

Attached the DXP Match file.
Match result from the perspective of Damage 12.4
22 Win 11 Lost and 125 Draw.
I don't think this result proves that Damage is better.
But I think it also fair to state that Damage is most likely not significantly worse,
and I assume with Dragon the 3 programs are in the same league.

I'm curious if there has been some progress (worth sharing and posting) with Damy and Maximus, and others....

Bert

[BertTuyt]

The Damage GUI DXP implementation also works for Dam 2.x and the Truus_DXP_Server.
With Dam 2.x Damage was able to complete the 158 games match.
Truus stopped however after 80 games, but this is most likely related to the resource leak problem of Truus.

I also will test the Flits_DXP_Server (where I dont expect problems) and Dragon.
Especially Dragon needs some work as the previous DXP trial did not work.
Maybe I need to work on a better internal DXP-Message timing and handling for the Damage GUI.

Bert

[BertTuyt]

The Damage GUI DXP is now tested with Dam 2.x, Flits_DXP_Server, Truus_DXP_Server, KingsRow and Dragon.
It all seem to work now (only in "Make Connection" so far).

The only 2 problems I faced:

- Truus stops after 80 (or so) games, but this is know behavior (Resource leak).
- The Dragon (64bit) Engine stops/fails after 8 -10 games, which is new to me...

I will work on the "wait for connection" implementation now...

If some people already want to test this implementation with Horizon, just drop me a line.

Keep you posted,

Bert

[Krzysztof Grzelak]

Certainly well the Horizon program is cooperating with the program Kingsrow. He isn't cooperating with the program Dragon. As for programs Truus and Flits it unfortunately I don't know because I didn't inspect it.

[BertTuyt]

Krzysztof, I have found a bug in my DXP-handler, which sometimes adds 2 DXP Messages into 1 string if the time between the DXP Messages is extremely short.

I test now every time if this is the case, and I hope the bug is now resolved.
Could you test it on your computer with Dragon?
In my case it seems to work, but the latest (64bit) Dragon Engine crashes after several games (could be related to my computer but I have not yet a clue).

The dropbox directory where you can find the latest Horizon 4.3: https://www.dropbox.com/sh/6wvpf978iissq8t/VbCC91w-bR

To run a DXP-match (without GUI) directly with Dragon, Dragon should be in a mode waiting for a connection:

The commands Horizon needs: ( don't type the // and text, it is just a comment )

opponents engine-engine
levelsfixedtime 2 // (so 2 seconds max.), with game adjudicate the game is around 1 minute (and some extra time as this version does not have a openings book yet)
$dxp client
$dxp match
$dxp prm m 65 // 65 moves
$dxp prm t 1 // 1 sec/move
$dxp go

Hope this works all....

Bert