Search Algorithm

[Krzychumag]

Bert thanks for 6P databases to programme Horizon. And you can throw open yet Opening Book to programme Horizon.

--Krzysztof.

[BertTuyt]

Krzysztof, thanks for your patience

As already shared, I'm planning to release the Horizon 4.1 Engine with related source (only the CSearch64 class still missing in action), in the next 2 weeks.
As there is still an unresolved bug in the parallel search (when running with a time constraint) my first priority is to solve that one, so all can benefit from multiple cores.
After this I start thinking about the Opening Book (how to generate and architecture) ...

Will keep you posted.

Bert

[BertTuyt]

Krzysztof, another question did you download the 6P databases already?

And if so how much time was involved?
Last but not least is it working in your case, for example at program start you should get the message
DB64 File Open = 155.

For 2P - 7P the corresponding number of files (at least in my case) is : 4 (2P) - 16 (3P) - 41 (4P) - 85 (5P) - 155 (6P) - 231 (7P)

Bert

[Krzychumag]

Hi Bert.

While downloading the file Databases downloaded the file from maximum with speed of my Internet connection. As for the program Horizon will wait of course. I will only add that in the version of program Horizon 4.0 error - when a program will be run on the board there are no divisions for the game.

-- Krzysztof.

[BertTuyt]

The parallel search seems to work.
The results in a match against Kingsrow (Kingsrow also with 4 cores) from the perspective of Kingsrow:
27 Win, 2 Lost, 129 Draw.
This yields an ELO difference of 55.
Attached the match file.

Bert

[BertTuyt]

Herewith the CSearch class.
The YBWC algorithm is mostly based on the work of Glaurung/Stockfish.

Also here the link to the Dropbox source folder...

https://www.dropbox.com/sh/sf7ynwmgo8ljf2j/6HkUp4CBwV

Bert

[BertTuyt]

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

[Krzychumag]

I thanks Bert. I have so request to You. Whether you can help me in correct placing the following window.



I have a processor Inter Core i3 350M from 8 GB of the memory of frames.

[BertTuyt]

If you have downloaded the 6P DB, then 2 GByte for the DB cache is sufficient.
DB max_piece should then be set to 6.
But i assume (although not tested) that nothing goes wrong if you keep the 7 value.
There is only a small time penalty involved, but possible not significant.

Bert

[Krzychumag]

I thanks of Bert. I still have such a question. Whether option " Permanent Brain " after marking her, he is acting correctly whether is out of order generally speaking.

[BertTuyt]

Permanent brain (or pondering) is not yet activated/implemented.

Bert

[Krzychumag]

Permanent brain (or pondering) is not yet activated/implemented.

Bert

Bert thanks for replies. I still have such three questions.

- write whether correct have am counting in Hash_Table
- write how much program has database - 6 or 7 databases
- whether you are working above latest version of the program.

[BertTuyt]

Bert thanks for replies. I still have such three questions.

- write whether correct have am counting in Hash_Table
- write how much program has database - 6 or 7 databases
- whether you are working above latest version of the program.

First of all, I slightly changed the Horizon version between the match against Kingsrow and posting it into Dropbox.
I found with this change I introduced a bug which negatively impacted the performance.
I corrected the bug (at least the one i was aware of), and reposted it.
So please replace the version you downloaded with the updated one.

If hope my interpretation of your questions is ok, if not please let me know:

* You dont need to change hash table settings, the current version has 128 MByte allocated which is sufficient.
* For now only the 6P DB is available via the download link i have issued in a previous post. I'm working on uploading the 7P DB to Skydrive. If it works I will issue the new link. For a slightly faster program you should change (for the moment) the DB_Max._Piece value into 6 (although with 7P the program also should work).
* For now I focus on the Horizon Engine (version 4.1), the Damage GUI is as is for now. I want to issue later this year a Horizon 4.2 and Horizon 4.3. The release criteria are for the 4.2 version that the ELO difference compared with Kingsrow is around 44 points ( so a 158 game match 20 - 0 - 138 ) for the 4.3 version this is 22 points ( 10 - 0 - 148). To defeat Kingsrow with Horizon 4.X is a bridge too far for now.

In the mean time im also running a 158 games match against Dragon PRO ( thanks to Michel). Dragon runs on 4 cores , is using the 6P DB (need to install 7P later), and game time is 10 min. Horizon 4.1 also uses 4 cores, has access to a 7P DB, and the game time is also 10 min.

After 49 games the score is so far (from the perspective of Dragon PRO) : 5 Win, 2 Lost, 40 Draw, 2 Unknowns. This yields (excluding unknowns) an ELO difference of 22 points.
If my information is correct (but Michel can confirm, or provide other/better info) Dragon PRO is around 18 points weaker compared with Kingsrow.
So with the result of Horizon 4.1 against Kinsgrow (ELO difference of 55 points), the result of Horizon 4.1 against Dragon so far seems consistent....

So I can agree with Michel that the non-registered version of Dragon PRO is most likely the best draughts freeware program so far.
And within this context Horizon 4.1 is the strongest open-source program around, as all source code has been published...

Will keep you all posted,

Bert

[BertTuyt]

Herewith the results of a short ( =80 games) match from Horizon 4.1 against Dragon Pro.
Both programs running on 4 cores , 10 min game time and no pondering.
Horizon has a 7P DB, Dragon used (this time) a 6P DB.
Match results (from the perspective of Dragon), 10 win, 3 lost, 67 draw.
This yields an ELO difference of around 30 points.
So remarkable consistent with the results of Horizon and Dragon against Kingsrow.

In the next days/weeks/... I will study Horizon improvement opportunities and whether I will be able to release a 4.2 version.
Again thanks to Michael and Ed for developing and releasing these beautiful programs !!

Walter, I count on you to find the evaluation improvement opportunities for Horizon

Will keep you posted,

Bert

[Walter Thoen]

Walter, I count on you to find the evaluation improvement opportunities for Horizon
Bert

Bert,

I would certainly want to help to improve the strengths of Horizon especially now that everything is open source.

I find it interesting to think about how a human would evaluate and how Horizon evaluates. For instance, Horizon seems to treat every node completely independent from the game position (i.e. from what is already known). The game position often has many features that do not change often but are critical for evaluation.

A position with a few pieces cannot change into a position with many pieces.
Tempi changes by +1 for a non-capture move. Tempi imbalances are causes by exchanges.
A classical game rarely changes into an attacking game and vice versa.
A lock (hekstelling etc.) usually persists for many moves.

Horizon does not seem to use the fact that these things rarely change during the game. Instead for every node Horizon seems to determine and calculate these things afresh. Would it not be more efficient to call the evaluation function with parameters based on knowledge from the game position? (e.g. call evaluation with is_klasiek = true for the entire search if is_klassiek is true in game position). Would it be more efficient to add tempi information to the node and update during movegen? (Note that it is only the tempi difference between white and black is important to conserve memory). Do you really have to recount to number of locked men for every node?

I also find the interaction between search and evaluation difficult to get my head around. For instance, in the Outpost (voorpost) evaluation the important questions are indeed 1) are there enough defenders? 2) will be defenders arrive on time? 3) are there other defenses than recapturing the attacker (opvangen)? Horizon attempts to answer the first two questions in the various Voorpost evaluation functions. The question whether the defenders will arrive on time is answered by calculating the distances. For a human the second question is probably more something for a restricted search. By a restricted search I mean a search that only considers moves that are relevant for the issue being evaluated. In this case only moves that are aimed at attacking or defending the outpost.

I think that a human uses such restricted or targeted searches a lot to evaluate a position. Is the outpost safe? Is a breakthrough possible? Who controls the wings? Could a computer implement this?

Some other areas that interest me personally are:

1) Add Killer-rule to Move Generator
2) Use CMoveGen64 code to get legal moves to Web GUI.
3) Use CDatabase64 code to retrieve end game db info with the Web GUI.
4) Try to get search to work massively parallel on Xeon Phi
5) 3-Hirn approach, i.e. start multiple searches with different parameters or eval in parallel and arbitrate best move.

Regards,
Walter