Search Algorithm

[Joost Buijs]

I have implemented (as is) the 8P DB-driver from Ed, and did some experiments with the Woldouby position.
First of all its close to a miracle to see a zero after many plies.

I also tested if different decrement depth methods would yield a difference in number of nodes, before the program finds a draw.
In below table I tested 3 methods.
1) Decrement depth always, 2) Decrement if number of moves > 1, 3) Decrement in case no capture move.

Next to that I included and excluded Internal Iterative Deepening in the case no hashMove was available.
Further no sorting, or killer, or History.

Code: Select all

Method            IID      Nodes         Ply
1) Always         Off	   253.347.095	30
1) Always         On	    206.719.204	30
2) Moves > 1      Off	   210.825.319	22
2) Moves > 1      On	    139.853.005	22
3) No Capture     Off	   248.610.432	20
3) No Capture     On	    138.422.730	20

In addition I added in the evaluation function if ( iXWhiteKing > 0 && iXBlackKing > 0) ) iEvaluation /= 2;

So far I only included DB-scan in the PVSearch and not the QSearch, which I also need to do, and then run tests again.

It amazes me that IID has such a big impact, this is probably because you have no other means of sorting yet.
With Ed's EGDB added I see the Woldouby draw at depth 28 (probing in quiescence), maybe I see the draw 2 ply earlier because I do promotions in quiescence.
Unfortunately I can't repeat your experiment atm., although Ed's EGDB is very fast it slows down my search by a factor 4 on positions like the Woldouby when I probe it in quiescence so I temporary removed it. Maybe I need a faster SSD on the PCI-e bus or larger memory for cashing, I still have to play with it a little.

Joost

[Joost Buijs]

Joost, yes there is little activity here.
Or all are working on secret improvements, or all have run out of ideas.

Bert, as you know, there is nothing secret to what I am doing https://github.com/rhalbersma/dctl
Also, earlier this month, I contributed some C++11 locking mechanisms to Ed's edgb driver https://github.com/eygilbert/egdb_intl/ ... ional_test

If there's anything you'd like to know, please ask!

I really wished you and Joost and others would just put your programs, or your GUI or anything else that is on Dropbox on GitHub. That makes it a lot easier to exchange ideas, small pieces of code etc.

Rein,

Although GitHub is included now in Visual Studio I have no intention of using it, I always think about GitHub of being very related to Linux and open-source. Since I'm not a very big fan of either Linux and open-source I don't feel the need to start using it. Exchanging ideas and code snippets can easily be done here at the forum as well.

Joost

[Rein Halbersma]

Joost, yes there is little activity here.
Or all are working on secret improvements, or all have run out of ideas.

Bert, as you know, there is nothing secret to what I am doing https://github.com/rhalbersma/dctl
Also, earlier this month, I contributed some C++11 locking mechanisms to Ed's edgb driver https://github.com/eygilbert/egdb_intl/ ... ional_test

If there's anything you'd like to know, please ask!

I really wished you and Joost and others would just put your programs, or your GUI or anything else that is on Dropbox on GitHub. That makes it a lot easier to exchange ideas, small pieces of code etc.

Rein,

Although GitHub is included now in Visual Studio I have no intention of using it, I always think about GitHub of being very related to Linux and open-source. Since I'm not a very big fan of either Linux and open-source I don't feel the need to start using it. Exchanging ideas and code snippets can easily be done here at the forum as well.

Joost

Hi Joost,

To each his own I guess As we discussed before, my main pleasure from this hobby comes from discovering new concepts in code and discussing that with others. Others derive pleasure from improving performance without disclosing their tricks. But next time you are wondering what people are doing, you now know where to look beyond this forum. There are several dozen draughts and checkers projects on GitHub, many of them inactive of course, but not all of them. I intend to seek contact with these people and who knows some of them might even come here to discuss stuff.

BTW, even if Git was developed by Linus Torvalds, GitHub as a platform is not in any way Linux-based. In fact, it has native GUI clients for OSX and Windows, but not for Linux! Another interesting thing: not only is Microsoft providing GitHub integration in Visual Studio, the company is now also actively opening up parts of their own sources. I find that very stimulating.

Rein

[Joost Buijs]

Bert, as you know, there is nothing secret to what I am doing https://github.com/rhalbersma/dctl
Also, earlier this month, I contributed some C++11 locking mechanisms to Ed's edgb driver https://github.com/eygilbert/egdb_intl/ ... ional_test

If there's anything you'd like to know, please ask!

I really wished you and Joost and others would just put your programs, or your GUI or anything else that is on Dropbox on GitHub. That makes it a lot easier to exchange ideas, small pieces of code etc.

Rein,

Although GitHub is included now in Visual Studio I have no intention of using it, I always think about GitHub of being very related to Linux and open-source. Since I'm not a very big fan of either Linux and open-source I don't feel the need to start using it. Exchanging ideas and code snippets can easily be done here at the forum as well.

Joost

Hi Joost,

To each his own I guess As we discussed before, my main pleasure from this hobby comes from discovering new concepts in code and discussing that with others. Others derive pleasure from improving performance without disclosing their tricks. But next time you are wondering what people are doing, you now know where to look beyond this forum. There are several dozen draughts and checkers projects on GitHub, many of them inactive of course, but not all of them. I intend to seek contact with these people and who knows some of them might even come here to discuss stuff.

BTW, even if Git was developed by Linus Torvalds, GitHub as a platform is not in any way Linux-based. In fact, it has native GUI clients for OSX and Windows, but not for Linux! Another interesting thing: not only is Microsoft providing GitHub integration in Visual Studio, the company is now also actively opening up parts of their own sources. I find that very stimulating.

Rein

Hi Rein,

Zero sum games like Chess and Draughts are competitive in nature, if everybody opens his source and reveals all his tricks there is not much of a competition anymore, but this doesn't necessarily mean that it is not nice to discuss many things regarding various algorithms and programming over here.

I wasn't wondering what others are doing, I only mentioned that it is not very inspiring that this part of the forum seems to be nearly dead and that there are hardly any computer tournaments to attend to. Writing a strong Draughts engine from scratch is many months of work and considering the lack of interest I started wondering if it is worthwhile to continue doing so, this is the dilemma I'm facing at the moment.

Joost

[Rein Halbersma]

Zero sum games like Chess and Draughts are competitive in nature, if everybody opens his source and reveals all his tricks there is not much of a competition anymore, but this doesn't necessarily mean that it is not nice to discuss many things regarding various algorithms and programming over here.

I wasn't wondering what others are doing, I only mentioned that it is not very inspiring that this part of the forum seems to be nearly dead and that there are hardly any computer tournaments to attend to. Writing a strong Draughts engine from scratch is many months of work and considering the lack of interest I started wondering if it is worthwhile to continue doing so, this is the dilemma I'm facing at the moment.

I am a big believer in Aiken's law: "Don't worry about people stealing an idea. If it's original, you will have to ram it down their throats."

[Joost Buijs]

Zero sum games like Chess and Draughts are competitive in nature, if everybody opens his source and reveals all his tricks there is not much of a competition anymore, but this doesn't necessarily mean that it is not nice to discuss many things regarding various algorithms and programming over here.

I wasn't wondering what others are doing, I only mentioned that it is not very inspiring that this part of the forum seems to be nearly dead and that there are hardly any computer tournaments to attend to. Writing a strong Draughts engine from scratch is many months of work and considering the lack of interest I started wondering if it is worthwhile to continue doing so, this is the dilemma I'm facing at the moment.

I am a big believer in Aiken's law: "Don't worry about people stealing an idea. If it's original, you will have to ram it down their throats."

I really don't worry about people stealing an idea, but what actually worries me is people taking the whole source-code, modifying a few lines and claiming the result to be their own original development, look at what happened in chess, this is mainly the reason that I switched to draughts 6 months ago.

Unfortunately there is not much activity over here, to me it feels like draughts has been solved and besides a few people nobody has interest anymore. Maybe this is true but on the other hand I have the feeling that computer-draughts is at the level that computer-chess was 10 years ago and that there is still a lot to gain.

10 years back when chess-programs were at the 2800 level we also saw a lot of draws, later came Rybka, Ippolit and derivatives, Stockfish and Komodo, and now the best chess-programs are at the 3400 level and there is still progress. Of course I can be wrong, maybe the level of the best humans and programs is already near the maximum you can reach with draughts, but I doubt it.

[TAILLE]

I am a big believer in Aiken's law: "Don't worry about people stealing an idea. If it's original, you will have to ram it down their throats."

I really don't worry about people stealing an idea, but what actually worries me is people taking the whole source-code, modifying a few lines and claiming the result to be their own original development, look at what happened in chess, this is mainly the reason that I switched to draughts 6 months ago.

Unfortunately there is not much activity over here, to me it feels like draughts has been solved and besides a few people nobody has interest anymore. Maybe this is true but on the other hand I have the feeling that computer-draughts is at the level that computer-chess was 10 years ago and that there is still a lot to gain.

10 years back when chess-programs were at the 2800 level we also saw a lot of draws, later came Rybka, Ippolit and derivatives, Stockfish and Komodo, and now the best chess-programs are at the 3400 level and there is still progress. Of course I can be wrong, maybe the level of the best humans and programs is already near the maximum you can reach with draughts, but I doubt it.[/quote]

I agree with you Joost, seeing the level of chess programs it is clear for me that the current draugths programs level is far from the maximum expected.
I have no problem by exchanging ideas around draughts program and BTW you saw in this topic I tried to answer all the questions I received. On the other hand I am quite reluctant to exchange code. Any guy claiming having a new draughts program has to do at least the coding effort hasn'it?

Gérard

[Yves]

Zero sum games like Chess and Draughts are competitive in nature, if everybody opens his source and reveals all his tricks there is not much of a competition anymore, but this doesn't necessarily mean that it is not nice to discuss many things regarding various algorithms and programming over here.

I wasn't wondering what others are doing, I only mentioned that it is not very inspiring that this part of the forum seems to be nearly dead and that there are hardly any computer tournaments to attend to. Writing a strong Draughts engine from scratch is many months of work and considering the lack of interest I started wondering if it is worthwhile to continue doing so, this is the dilemma I'm facing at the moment.

I am a big believer in Aiken's law: "Don't worry about people stealing an idea. If it's original, you will have to ram it down their throats."

Hello everyone
Thanks to you programmers.
Keep sharing your ideas on the forum.
This allows Internet users to progress to the game of draughts.
Yves

[BertTuyt]

Herewith my 5 cents....

For whatever reason I guess we are 300 ELO away from perfect play.
When KingsRow arrived, I had a hard time catching up.
The same was valid for the Truus and Flits era, a long time ago (in a parallel universe).
And then Scan arrived, who raised the performance bar with 30 ELO.
Not only that, Fabien revealed all source code and insights, and despite sharing Scan also won the next Olympics.
For me Fabien (and also Harm) are great examples, and I'm very thankful what they do and did.

With Damage I was twice Open Dutch champion.
I shared first place twice but lost the tiebreak (Against Flits and Buggy ).
Regarding 2nd (example Olympics 2015) and 3th places I lost count, will check in the next days .
So basically I don't need to prove anything anymore (I Hope ).

I'm now restarting with Dwarf (once in a while you need to start with a clean sheet), although ultimate it will be renamed in Damage (Version 14).
Goal is (not easy, or mission possible?) to bypass Scan 2.0
But in the spirit of Fabien and Harm, I will post all results here, and share all sources........
Because I also believe that sharing is much more fun, and for me community contribution recognition is more important as becoming 1 once in a while.

Bert

[BertTuyt]

Forgot to mention the contribution of Ed (who I also admire), with his work on the 8P DB, and sharing Driver sources....
Sorry Ed, for not mentioning you in the first post.
And Joost welcome here, you provide much energy to this forum.
And to all my other (sleeping) Computer Draughts Friends, please wake up, I'm sure you have much value to add towards the equation.
Especially Michael, where are you

Bert

[Krzysztof Grzelak]

Herewith my 5 cents....

For whatever reason I guess we are 300 ELO away from perfect play.
When KingsRow arrived, I had a hard time catching up.
The same was valid for the Truus and Flits era, a long time ago (in a parallel universe).
And then Scan arrived, who raised the performance bar with 30 ELO.
Not only that, Fabien revealed all source code and insights, and despite sharing Scan also won the next Olympics.
For me Fabien (and also Harm) are great examples, and I'm very thankful what they do and did.

With Damage I was twice Open Dutch champion.
I shared first place twice but lost the tiebreak (Against Flits and Buggy ).
Regarding 2nd (example Olympics 2015) and 3th places I lost count, will check in the next days .
So basically I don't need to prove anything anymore (I Hope ).

I'm now restarting with Dwarf (once in a while you need to start with a clean sheet), although ultimate it will be renamed in Damage (Version 14).
Goal is (not easy, or mission possible?) to bypass Scan 2.0
But in the spirit of Fabien and Harm, I will post all results here, and share all sources........
Because I also believe that sharing is much more fun, and for me community contribution recognition is more important as becoming 1 once in a while.

Bert

Unfortunately, Bert but one thing you have to prove yourself and other people at the forum.

[BertTuyt]

Krzysztof,

your constructive positive feedback is a great asset, and a motivation to do the impossible.
I'm glad you a part of our community, and would miss the witty remarks, and philosophical thoughts.

Bert

[Krzysztof Grzelak]

I really don't worry about people stealing an idea, but what actually worries me is people taking the whole source-code, modifying a few lines and claiming the result to be their own original development, look at what happened in chess, this is mainly the reason that I switched to draughts 6 months ago.

Unfortunately there is not much activity over here, to me it feels like draughts has been solved and besides a few people nobody has interest anymore. Maybe this is true but on the other hand I have the feeling that computer-draughts is at the level that computer-chess was 10 years ago and that there is still a lot to gain.

10 years back when chess-programs were at the 2800 level we also saw a lot of draws, later came Rybka, Ippolit and derivatives, Stockfish and Komodo, and now the best chess-programs are at the 3400 level and there is still progress. Of course I can be wrong, maybe the level of the best humans and programs is already near the maximum you can reach with draughts, but I doubt it.

I agree with you Joost, seeing the level of chess programs it is clear for me that the current draugths programs level is far from the maximum expected.
I have no problem by exchanging ideas around draughts program and BTW you saw in this topic I tried to answer all the questions I received. On the other hand I am quite reluctant to exchange code. Any guy claiming having a new draughts program has to do at least the coding effort hasn'it?

Gérard

Very strange and very mistakenly think you Gerard. Not all are thieves code. Think about the people who love programs drafts.

[Krzysztof Grzelak]

Krzysztof,

your constructive positive feedback is a great asset, and a motivation to do the impossible.
I'm glad you a part of our community, and would miss the witty remarks, and philosophical thoughts.

Bert

And what it is impossible to do Bert.

[BertTuyt]

Nothing is impossible, the word itself says 'I'm possible'! Audrey Hepburn
It always seems impossible until it's done. Nelson Mandela
Progress is impossible without change, and those who cannot change their minds cannot change anything. George Bernard Shaw
Start by doing what's necessary; then do what's possible; and suddenly you are doing the impossible. Francis of Assisi
Impossible is a word to be found only in the dictionary of fools. Napoleon Bonaparte
Everything is theoretically impossible, until it is done. Robert A. Heinlein
There is nothing impossible to him who will try. Alexander the Great
In order to attain the impossible, one must attempt the absurd. Miguel de Cervantes


Bert