World Draughts Forum

It is currently Mon Dec 17, 2018 18:29

All times are UTC+01:00




Post new topic  Reply to topic  [ 712 posts ]  Go to page Previous 144 45 46 47 48 Next
Author Message
 Post subject: Re: Search Algorithm
PostPosted: Sat Apr 08, 2017 20:38 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1612
Fabien Letouzey wrote:
BertTuyt wrote:
And last but not least, do you already have a gut feel whether this is (with perfect play) a white or black win?

No.

We already know that white wins in 8x8 (with checkers capture rules anyway), so that is a strong indication. On the other hand, I put Draughts into the "blocking game" category (with Othello) so it's also possible that white has to self-destruct first.


I think that the game result depend on the rules, in particular the king range. For what it's worth, about 6 years ago, I did some computations on the 6x6 board for all game variants. The results have not been published before, but I shared them with Ed in private communication (October 19, 2011).

Quote:
============

I have weakly solved all 6x6 draughts and checkers variants, both the regular game and the suicide (AKA giveaway, misere or qui-perd-gagne) variety. This was a neglected corner of the solving small games literature http://en.wikipedia.org/wiki/Solved_game

The method used was a simple alpha-beta search (pvs and iterative deepening enhancements). No endgame databases were used. The games are therefore not strongly solved because there could conceivably be endgames which take more than reasonable resources to be resolved by forward search only. Strongly solving all these games (i.e. building the complete 12-piece databases) is also well within current technology (somewhat less than the 7-piece databases for the 10x10 game).

Compared to the Chinook project of solving 8x8 checkers (2007), Martin Fierz's probable draw solution for 8x8 suicide checkers (2010), and the recent announcement of the white win in 8x8 Russian suicide by Osipov and Morozev (2011), this was a nano-step for mankind. The searches took less than 15 minutes each on a 3.2 Ghz P4 with 1Gb of hash tables. The number of nodes are less than 1e9 per solution, somewhat in between solving 5x5 Amazons and 6x6 Othello.

Below are the results (W59 means white wins in 59 plies, L28 means white loses in 28 plies etc.). For a detailed description of the different rules, see the perft thread on this forum or the excellent website http://www.mindsports.nl/index.php/on-t ... s-variants

Code:
Variant         Regular Suicide
-------------------------------
International   DRAW    W36
Killer          W59     W36
Frisian         L28     L27
Pool            DRAW    W34
Russian         DRAW    W34
Thai            DRAW    W38
Czech           DRAW    W32
Spanish         DRAW    W32
Italian         DRAW    DRAW
Checkers        DRAW    DRAW

Interestingly, the results for 6x6 Russian suicide (white win) and 6x6 checkers suicide (draw) match the results for the 8x8 board. Also notable is that only the games with short ranged kings have drawn suicide games.

The drawn games in the table above are not 100% guaranteed because my search does not take care of Graph-History-Interaction. On the other hand, the search engine (a series of C++ templates) was extensively unit-tested on the 4-piece databases for International and Killer draughts, without encountering any discrepancies between the forward search and the database results (with forward searches of up to 77 plies). Nevertheless, any confirmation would be welcome!


These results should be taken with some disclaimer because of the Graph-History Interaction. With current technology, these 6x6 games could also be strongly solved (i.e. the opening position fits within the endgame databases). Also, I didn't compute the breakthrough results.

In any case, assuming correctness, note that Killer and Frisian are the only decided games on a 6x6 board, and with give-away, only the short-ranged king games (Italian and Checkers) are a draw. The Russian give-away game has also been solved to be a white win on a 8x8 game board (can't find the link anymore), most likely with far less resources than was required to proof 8x8 checkers to be a draw.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sat Apr 08, 2017 20:43 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1612
Fabien Letouzey wrote:
Ah, I see. Well in general, mobility is still important in "losing games", so blindly giving away material is not recommended. But it makes your point clear now: we don't know what to put in evaluation, but learning probably will; better than our guesses anyway.


The Russian version of Wikipedia on give-away draughts has a section on strategy (use Google Translate).

Quote:
Mark Watkins solved losing chess last year; white wins with 1. e3. A few black responses took a long time to refute. PDF at http://magma.maths.usyd.edu.au/~watkins ... GA2016.pdf
It's relevant because captures are mandatory and the king loses its special status, making this variant "draughts-like".


Yes, I read about it, but haven't studied in detail. 200-300 core years sounds like serious resources, more than a single man effort could do :)


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Apr 09, 2017 12:17 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith the results for the PST based search (without the 22 - 20 match).

Attachment:
Table Scan Deep Search DE2.png
Table Scan Deep Search DE2.png [ 10.85 KiB | Viewed 4793 times ]


The results of the 4 different eval tests are summarized in below graph.
The PST Match is represented with the yellow line.
Basically match results are as expected.
Also here the initial model doesn't seem to hold, as the exponent seems to be related to eval strength.

Attachment:
Scan Deep Analysis DE2.png
Scan Deep Analysis DE2.png [ 57.52 KiB | Viewed 4793 times ]


I will today not focus on the 22-20 PST match, but run some tests with PST against the full eval.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Apr 12, 2017 19:53 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
I have now some results for the Scan - Scan match, where 1 player has a FULL eval, and the other a PST and 2 ply search more.
As expected the FULL eval wins easily.
I did not complete the 22-20 match due to a restart during the night, but think 154 games would be sufficient.
Below results.

Attachment:
Scan Deep Analysis FPST.png
Scan Deep Analysis FPST.png [ 27.61 KiB | Viewed 4604 times ]


Attachment:
Table Scan Deep Search FPST.png
Table Scan Deep Search FPST.png [ 11.38 KiB | Viewed 4604 times ]


Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Apr 17, 2017 16:47 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Started a match between 2 identical versions of Scan (24 ply search and 22 ply search).

This time on my faster computer (so 8 core 4 GHz).
The 24 ply games take around 20-25 minutes per game, so very much comparable with standard tournament settings.

Match still running, will be finalised tomorrow ( = Tuesday), but after 116 games, the first win for the deeper search (24 ply) version (and 115 draws).
This translates ( so far) in a 3 Elo rating difference.....

Guess this is the future of Computer Draughts (comparable with the checkers matches these days most likely).

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Tue Apr 18, 2017 11:24 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
The match (24 ply Scan against 22 ply Scan) ended with 157 draws and 1 win for the 24 ply search.
See below the update table and graph.
Attachment:
SDA Table.png
SDA Table.png [ 10.41 KiB | Viewed 4491 times ]


Attachment:
SDA Graph.png
SDA Graph.png [ 29.19 KiB | Viewed 4491 times ]


So it becomes clear that we need more knowlegde (as Fabien already predicted) to really further (significant) improve Draughts Engines.
Increasing the search depth will only further increase ELO rating in a limited way (as the matches indicate).
Also not sure if we can predict how far we are from perfect play.

If we can translate this trend towards perfect play (based upon these results), and assume that we maintain a constant increase of 2 - 5 ELO point till ply 64 (just an arbitrary number, and not in line with exponential decrease), than there are still (best case) (64-24)/2 = 20 times 2 - 5 points to gain, so resulting in 40 - 100 points.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Apr 19, 2017 09:24 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 244
It all seems to go to draw and perfection pretty fast at this level.

Maybe it is time for everyone to switch to breakthrough-draughts :-) Surely there is room for competition there.

I'll do some independent test, but that needs to wait a couple of weeks for my computer is working out some new algorithmic ideas.

Michel


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Apr 19, 2017 12:13 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
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.

Quote:
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Tue May 02, 2017 18:20 
Offline

Joined: Mon Oct 17, 2016 09:05
Posts: 17
Real name: Robin Messemer
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Tue May 02, 2017 21:02 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Yes several Draughts programs use an aspiration window.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed May 03, 2017 18:50 
Offline

Joined: Mon Oct 17, 2016 09:05
Posts: 17
Real name: Robin Messemer
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun May 07, 2017 13:43 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 274
Real name: Fabien Letouzey
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Tue May 16, 2017 14:37 
Offline

Joined: Mon Oct 17, 2016 09:05
Posts: 17
Real name: Robin Messemer
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sat Sep 09, 2017 12:56 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 712 posts ]  Go to page Previous 144 45 46 47 48 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited