Computer Draughts 2011

Discussion about development of draughts in the time of computer and Internet.
BertTuyt
Posts: 1477
Joined: Wed Sep 01, 2004 19:42

Computer Draughts 2011

Post by BertTuyt » Mon Jan 03, 2011 23:55

First of all the best wishes to all of you, and everyone near to you.

As I still enjoy holiday, I was thinking about my things to do list related to Computer Draughts.
Here is mine , I'm very interested in the response of others....

To DO:
* Improvements in the search efficiency (as I still believe Kingsrow out searches Damage in critical positions)
* Improvements in the Eval functions (as a result of match play)
* Improvements in the Endgame DB, I guess I to much approach the DB SSD in situations where it is not really needed.
* More matches against KingsRow (if Ed agrees :) )
* Communicate often in this forum

Don't DO
* I will not start with the generation of the 8p DB (see next item).
* I will not buy a new computer. I will wait for 2012, and then i hope to get my 16 core ( 2 Sandy Bridge Processors) 48 GByte + 500 GB SSD computer system :)
* I will most likely not participate in any tournament, as I don't expect to have a significant better program as compared with 2010 (which for me always was a reason to compete)

Next to that I hope competition will also improve :), in 2011 every program really should have 7p DB's and parallel search ................

Bert

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Computer Draughts 2011

Post by MichelG » Tue Jan 04, 2011 10:04

Best wishes to all...

My todo list for dragon:
- I have written a completely new GUI. The plan is to finish it and make it available for download
- Further increase parallel efficiency (now at 2.7 for 4 cores and 3.3 for 6 cores)
- Try to improve the core evaluation function. I think this is very hard though
- There is a lot of RAM available. The plan is to make more use of it by increasing the size of precomputed tables (like the breakthrough tables and evaluation parameters)
- Join for some tournament

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Computer Draughts 2011

Post by TAILLE » Tue Jan 04, 2011 10:23

Happy new year for all ...

2010 was for Damy the year of
1) a parallel search algorithm (till 2009 I used only a 2 threads algorithm but now Damy is able to use 8 threads)
2) the 8 pieces db (today Damy has 100% of 4x4db and 80% of 5x3db)
I hoped to work on the damExchange protocol but I did not find time for that

For 2011 :
1) I have still to stabilise my new algorithm
2) I have to work on the best way to use the new 8 pieces db
3) I have in mind some major improvments for the evaluation function
4) I hope to find time enough to work on the damExchange protocol and play a first match through internet

Gérard
Gérard

Rein Halbersma
Posts: 1700
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Computer Draughts 2011

Post by Rein Halbersma » Tue Jan 04, 2011 10:57

Best wishes for everyone,

2010 was the year when Mistral became <Mistral> (yes the brackets are part of the name, for those of you who know C++ templates)

2011 will hopefully be the year when I:
1) finish the implementation of DamExchange
2) connect to a CheckerBoard or GUIDE like GUI
3) play a online match
4) play a real life tournament

Rein

Ed Gilbert
Posts: 808
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Computer Draughts 2011

Post by Ed Gilbert » Tue Jan 04, 2011 13:58

Best wishes to all in this new year.

2010 was the year in which I broke my foot, and since I couldn't run for 3 months I spent more time working on kingsrow :-). It was also the year in which I made kingsrow available for purchase. Having a bunch of draughts experts use your program is a good way to identify weaknesses and make improvements.

I have lots of ideas to try in 2011, and not enough computer cores to test them all. Computer draughts continues to be a fun hobby.

-- Ed

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

Re: Computer Draughts 2011

Post by BertTuyt » Wed Jan 05, 2011 19:43

Michel, you stated:
I have written a completely new GUI. The plan is to finish it and make it available for download
I this the 3.0 Beta version , now available as download on your web page, or something completely new?
When do you think you will issue the next draft/final version ?
Is it GUIDE protocol based, or something different?

I think this is a great opportunity to realize a common GUI for everyone, so I'm also interested if it contains all the features of my own GUI ( Damage 2000).
Is it possible that we discuss within this forum wishes/features we would like to see......

Bert

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Computer Draughts 2011

Post by MichelG » Tue Jan 11, 2011 13:18

BertTuyt wrote:Michel, you stated:
I this the 3.0 Beta version , now available as download on your web page, or something completely new?
When do you think you will issue the next draft/final version ?
Is it GUIDE protocol based, or something different?
Bert
What i did was take the vb6 source code of the gui, and rewrote it using visual basic dotnet and c#. For the most part the gui functions the same, and i have redesigned some other functions. I dropped the 3d-interface because that was too much work to recode for now.

It still uses guide, so i guess that should still work :-)

It will probably take a while before it is released, at the moment i am focusing on getting the engine to play better.

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Computer Draughts 2011

Post by jj » Sun Jan 16, 2011 18:27

Although technically too late, still best wishes to you all.

I don't know if you already know this, but in Russia Programmers' Day is an official professional holiday, celebrated on the 256th day of each year (September 13 during common years and on September 12 on leap years). So the annual Dutch Open computer tournament was held at appropriate days the last two years ;-)

Maximus is improving but not yet ready for the strongest opponents. Here something about my status and plans, which will probably extend this year :-( :-)

I managed to get YBWC alphabeta running by the end of last year. Starting from scratch with parallel perft, then parallel minimax, then parallel alphabeta. All with a hash table that can be switched off. I can recommend these steps for anyone writing a new program (or testing an existing one), since all steps and options can be verified apart and combined, saving time in debugging.
In my experience (too), fixed depth parallel searches only produce different results in combination with a hash table, due to the GHI problem (haven't solved this yet).

After finding out that Java Object overhead is 24 bytes per object –so in my case per hash table entry– I wanted to change the implementation. With 32 bytes of data per entry this is way too much overhead! As Java doesn't support structs I flattened the table to an array of 64-bit longs. This is one of the few times I felt I had to do something awkward in Java as compared to C++.
Then I also changed (had to) from entry locking (overhead not too bad) to Hyatts idea of a lockless hash table.

Finally, I added the History Table again and made a few changes to the evaluation function. The evaluation is still not very advanced but at least it's fast. (I did not consider duplicating code for white and black.)
It does, however, use a 160 MB breakthrough table for all possible passed men on the last 5 ranks (minus the kingsrow).
Performance on the i7-920 quad core 2.8 GHz is almost 19.5 Mnodes/sec using 8 threads (hyperthreading). Quite a monster. Parallel scaling is factor 4.23 for nodes/sec and factor <3.4 for time-to-depth.

No egdb yet. I plan to use (only) the 6 pieces database from Michel and Harm, as I did in ABCdam. Must see how Java memory management holds well with this.
How bad is missing the 7 pieces db?

I played two DXP matches, each consisting of (the first) 64 ballot games, against the classic opponents.

Maximus 8CPU (10 sec/move) vs. Dam2.2 (75 in 10 min): +11 –0 =53 (59%)
Maximus 6CPU (15 sec/move) vs. Flits (75 in 10 min, with pondering): +3 –13 =48 (34%)

At least this was a good performance and "correctness" test.
By the way, I agree that it is too bad pondering cannot be switched off in Flits.

As I am also interested in learning to play a decent game myself, a long to be fulfilled wish is writing a better evaluation function. I also enjoy mailing with an experienced draughts player who has also started writing his own program. The losses to Flits I can (now) easily spot as gaps in the Maximus evaluation function.

At the moment I am struggling with MTD-f (failing low in the root) and time management. Other plans include some new stuff for me like fixing GHI, pruning and search extensions. And improving on the ABCdam opening book and pondering. Maybe I'll have a look at GUIDE as well.

I learn a lot from this forum and its regular contributors. If I can help with any questions or (limited :-)) curiosity please let me know.

Jan-Jaap
www.maximusdraughts.org

Ed Gilbert
Posts: 808
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: Computer Draughts 2011

Post by Ed Gilbert » Sun Jan 16, 2011 23:58

Hi JJ,

Nice to hear that you continue to be actively improving maximus. Your parallel search performance sounds very good, especially considering some of the things you have to overcome in Java.
How bad is missing the 7 pieces db?
I think it is a relatively minor improvement in engine matches. With the 7pc db you might win a few more games in a match of 2-move ballots, or eke out a draw when you're losing, but it will not be a big difference. The main benefit is for people that want to know the absolute win/loss/draw truth about endings. The things you mentioned as future plans are more important.

-- Ed

jj
Posts: 180
Joined: Sun Sep 13, 2009 23:33
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands

Re: Computer Draughts 2011

Post by jj » Mon Jan 17, 2011 10:26

Ed Gilbert wrote:
How bad is missing the 7 pieces db?
I think it is a relatively minor improvement in engine matches. With the 7pc db you might win a few more games in a match of 2-move ballots, or eke out a draw when you're losing, but it will not be a big difference. The main benefit is for people that want to know the absolute win/loss/draw truth about endings. The things you mentioned as future plans are more important.
OK Ed, thanks.
www.maximusdraughts.org

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

Re: Computer Draughts 2011

Post by BertTuyt » Sun Feb 13, 2011 16:01

Based on all recent discussions, I want to dig (during this sabbatical without tournaments :o ) into the automatic learning aspects of computer programs (and especially related towards evaluation function learning).
Does somewhat have specific experience with this, and/or literature,examples, which i can use as a starting base?

Your advice and suggestions are welcomed and appreciated....

Bert

User avatar
Marcel Kosters
Posts: 2224
Joined: Mon Jan 20, 2003 16:13
Location: Haarlem, The Netherlands

Re: Computer Draughts 2011

Post by Marcel Kosters » Mon Feb 14, 2011 11:49

BertTuyt wrote:Based on all recent discussions, I want to dig (during this sabbatical without tournaments :o ) into the automatic learning aspects of computer programs (and especially related towards evaluation function learning).
Does somewhat have specific experience with this, and/or literature,examples, which i can use as a starting base?

Your advice and suggestions are welcomed and appreciated....

Bert
My 5 cents and I'm not sure if this is correct as I only heard it from a layman such as myself. But maybe Stef Keetman from Truus knows more about this subject. As I understood it (yet again from another layman), Keetman was working on automatic learning aspects in Truus.
Nu: 28.200 DamZ! DamSets. Doel: 100.000 DamZ! DamSets zo snel mogelijk. Doe mee met 1, 10 of 100 DamZ! DamSets. De strategie is onbeperkt schaalbaar. Met club of vrienden snel besteld via marcelkosters@gmail.com.

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

Re: Computer Draughts 2011

Post by BertTuyt » Mon Feb 14, 2011 20:26

Marcel, I have the Stef Keetman document about automatic combination pattern learning.
But what I'm looking for, is automatic pattern detection for evaluation functions...

Bert

User avatar
Marcel Kosters
Posts: 2224
Joined: Mon Jan 20, 2003 16:13
Location: Haarlem, The Netherlands

Re: Computer Draughts 2011

Post by Marcel Kosters » Mon Feb 14, 2011 22:17

Ok, about that I certainly do not know anything. I leave the discussion to the specialists again.
Nu: 28.200 DamZ! DamSets. Doel: 100.000 DamZ! DamSets zo snel mogelijk. Doe mee met 1, 10 of 100 DamZ! DamSets. De strategie is onbeperkt schaalbaar. Met club of vrienden snel besteld via marcelkosters@gmail.com.

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: Computer Draughts 2011

Post by TAILLE » Mon Feb 14, 2011 23:56

BertTuyt wrote:Marcel, I have the Stef Keetman document about automatic combination pattern learning.
But what I'm looking for, is automatic pattern detection for evaluation functions...

Bert
Hi Bert,

Oops, it seems that I did not understand what you were trying to do. For me "automatic pattern learning" meant learning through a great number of games which looked to me quite impossible for a complex game like draughts. Now you use the wording "automatic pattern detection" which is quite different. By replacing the word "learning" by the word "detection" the problem becomes completly different. The goal is not to discover new patterns through a great munber of games but to detect the patterns of a given game and to evaluate it even if this pattern have never been identified before.
BTW I am working hard on this latter subject and I discovered a new (secret) idea that told me that this approach migth be very efficient. I will soon be able to begin the first tests ... against Kingsrow.
Gérard

Post Reply