Search Algorithm

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Fabien Letouzey
Posts: 299
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Search Algorithm

Post by Fabien Letouzey » Wed Apr 19, 2017 12:13

Hi Michel,
MichelG wrote:It all seems to go to draw and perfection pretty fast at this level
It looks scary, but that's self-play. There is also the remote possibility that I prune too much with increasing depth, making "late plies" weaker and weaker. I only test using fast games.

There is one aspect in Bert's experiments that is worrying me, however: the better the eval, the worse the diminishing returns. This seems to suggest that if we improve evaluation, search won't matter anymore.
Maybe it is time for everyone to switch to breakthrough-draughts :-) Surely there is room for competition there.
Exactly! Who needs kings anyway? ;) Better hurry before Bert solves it on his computing monster, though.

Speaking of breakthrough. I've just computed an evaluation for this variant, and it's better than the generic one. Presumably it focuses on emulating a breakthrough table. I have no idea whether midgame strategy is actually different; I hope not.

I was comparing two evaluations, and did this with two different time controls: game in 1s and game in 4s. Both tests gave the same result. So this reinforces your theory that wilo remains constant with increasing depth/time. Furthermore, without draws, wilo = Elo so the unit is meaningful (and hopefully additive).

I also expect Killer draughts to stay interesting for a few years, but there's little doubt that it's going to follow the same fate eventually ... In both variants, I feel that there is a better balance between search and evaluation. In that context, working on search still makes sense.

Fabien.

CheckersGuy
Posts: 20
Joined: Mon Oct 17, 2016 09:05
Real name: Robin Messemer

Re: Search Algorithm

Post by CheckersGuy » Tue May 02, 2017 18:20

Hey,
Do you use aspiration windows in your draughts engine ? Is it worth implementing ? What I have read so far about aspiration windows is that it does help quite a bit when most evaluations only differ slightly (At least in chess engines it does help). I thought this might help in the endgame when my engine hits the endgame tablebase.

Would like to know what you guys think

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Tue May 02, 2017 21:02

Yes several Draughts programs use an aspiration window.

Bert

CheckersGuy
Posts: 20
Joined: Mon Oct 17, 2016 09:05
Real name: Robin Messemer

Re: Search Algorithm

Post by CheckersGuy » Wed May 03, 2017 18:50

BertTuyt wrote:Yes several Draughts programs use an aspiration window.

Bert
Thats cool. May I ask how wide your window is ? I implemented aspiration Windows now and started with a very large window but I haven`t had the time to test it yet.


Robin

Fabien Letouzey
Posts: 299
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Search Algorithm

Post by Fabien Letouzey » Sun May 07, 2017 13:43

There is a discussion about Wilo on the chess forum: http://www.talkchess.com/forum/viewtopi ... _view=flat
It seems to have all the good properties that we hoped.

Fabien.

CheckersGuy
Posts: 20
Joined: Mon Oct 17, 2016 09:05
Real name: Robin Messemer

Re: Search Algorithm

Post by CheckersGuy » Tue May 16, 2017 14:37

Hey,
are most engines using some version of YBW (Young brothers waint concept) for parallel search ? I tried lazy smp which seems to be quite popular among the chess engine scene nowadays. However, the speedup wasn`t much at all which means that I either implemented it incorrectly or lazy smp might not work very well in Checkers/Draughts.
Would like to know what your parallel search is based on and where I could find a paper about YBW or PseudoCode.

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Sep 09, 2017 12:56

Sorry i forgot to answer this question.

In my case the parallel search is based upon YBWC, and my inspiration was Stockfish.
I don't have a paper, but browsing through he Stockfish source code is quite self explaining.

Bert

Post Reply