Search Algorithm

[Catherine]

Thanks for the reply, it is clear now, this elo difference is too big 300, i understand why Dragon win almost all his game against Dam 2.2. I havent Kingsrow yet to do a test. Thank again

[BertTuyt]

I have now added the :piececount keyword in DQL.
See below code.

Code: Select all

; Example :piececount 1-jan-2014
(match
(position m13 m14 m15 m20 m25 M24 M29 e19 e30 :btm :equal :piececount M[35,40,44,45,49,50] 0)
)
; end example

In the TurboDambase (2005 version) 424 matches were found...

Bert

[BertTuyt]

Added the :result keyword in DQL
syntax :result w/d/l (Win, Draw, Lose, all perspective white)

Code: Select all

Example :piececount + :result 3-jan-2014
(match
:result l
(position m13 m14 m15 m20 m25 M24 M29 e19 e30 :btm :equal :piececount M[35,40,44,45,49,50] 0)
)
; end example

Pattern game match (based on TurboDambase 2005)
win 148, draw 144, lose 132

Bert

[BertTuyt]

I recently studied the 1man - 1man database, for no other reason than curiosity (as it has little practical use).
The question which I still wanted to resolve if all 3970 possible 1-1 positions (1985 * 2 ,so white or black to move) are possible.

After 2G ( 2.000.000.000) Monte Carlo simulations the programs really seems to stabilize on 3934, so 36 positions missing.
I modified the program so it now lists these positions at the end of the simulation.

The verdict:
* Every possible position in terms of white on a legal square and black on a legal square was found.
* But for 18 white to move , and 18 black to move positions (and they are indeed mirrored !), it seems to be impossible to realize them trough normal game play.

Below one example, and also the total list of illegal positions.
Maybe I have overseen something, so I'm open for any suggestion how to get there...

Here just an example, (first example form the list) with Black to Move:




So the question here how is it possible for the White piece to get to 6, while the square on 11 is occupied, and a capture via a different path seems to be impossible...

TWB = Turn (white/black), white piece coordinate, black piece coordinate

Code: Select all

TWB: Black, 6, 11
TWB: Black, 6, 17
TWB: White, 7, 1
TWB: White, 7, 2
TWB: White, 8, 2
TWB: White, 8, 3
TWB: White, 9, 3
TWB: White, 9, 4
TWB: White, 10, 4
TWB: White, 10, 5
TWB: White, 10, 15
TWB: White, 11, 16
TWB: White, 12, 1
TWB: White, 14, 5
TWB: Black, 15, 20
TWB: Black, 16, 21
TWB: White, 20, 25
TWB: White, 21, 26
TWB: Black, 25, 30
TWB: Black, 26, 31
TWB: White, 30, 35
TWB: White, 31, 36
TWB: White, 34, 45
TWB: Black, 35, 40
TWB: Black, 36, 41
TWB: White, 40, 45
TWB: Black, 46, 37
TWB: Black, 46, 41
TWB: Black, 47, 41
TWB: Black, 47, 42
TWB: Black, 48, 42
TWB: Black, 48, 43
TWB: Black, 49, 43
TWB: Black, 49, 44
TWB: Black, 50, 39
TWB: Black, 50, 44

Bert

[BertTuyt]

I have recently increased my computer memory from 12 GByte towards 24 GByte.
Unfortunately this (older) motherboard could not cope with 8 GByte Dimms, otherwise I could expand memory to 48 GByte ( 6 * 8 GByte).

With this increase I was able to simulate another (useless) database.
This time I tested how many kings white could get from the initial position, with black still having 20 man.
The answer ( without detailed verification) seems to be 5, and the maximum move sequence is 123 ply.

More details in below table.
The number for positions is including all possible king configurations.

Code: Select all

King	  Positions	   Delta	   Ply
0	     3038453122                77
1	     3977790903	939337781	 110
2	     4328092211	350301308	 114
3	     4386255504	58163293	  119
4	     4388320839	2065335	   119
5	     4388374518	53679	     123
6	     4388374518	0	

Bert

[Rein Halbersma]

I have recently increased my computer memory from 12 GByte towards 24 GByte.
Unfortunately this (older) motherboard could not cope with 8 GByte Dimms, otherwise I could expand memory to 48 GByte ( 6 * 8 GByte).

With this increase I was able to simulate another (useless) database.
This time I tested how many kings white could get from the initial position, with black still having 20 man.
The answer ( without detailed verification) seems to be 5, and the maximum move sequence is 123 ply.

More details in below table.
The number for positions is including all possible king configurations.

Code: Select all

King	  Positions	   Delta	   Ply
0	     3038453122                77
1	     3977790903	939337781	 110
2	     4328092211	350301308	 114
3	     4386255504	58163293	  119
4	     4388320839	2065335	   119
5	     4388374518	53679	     123
6	     4388374518	0	

Bert

That is a nice computation, Bert! Do you have the game notation of that 5K-20M game?

[BertTuyt]

Rein, as with the previous calculation it is not simple to retrieve the initial move sequence (although not impossible).
Maybe I will give it a try, as this is another world record, 123 moves (ply) without captures .
For your reference the positions are all without capture. So white has (in the end, in the last simulation) 15 man + 5 king and black 15 man.

Going into kings on both sides is more difficult as my method no longer works, and you have to deal with all kind of cycles, and cycle-detection.

Bert

[Rein Halbersma]

Rein, as with the previous calculation it is not simple to retrieve the initial move sequence (although not impossible).
Maybe I will give it a try, as this is another world record, 123 moves (ply) without captures .
For your reference the positions are all without capture. So white has (in the end, in the last simulation) 15 man + 5 king and black 15 man.

Going into kings on both sides is more difficult as my method no longer works, and you have to deal with all kind of cycles, and cycle-detection.

Bert

Somewhere on this forum there is a ~400 ply game that ends in 20 kings vs 20 kings.

[BertTuyt]

Rein, yes I heave seen the statement on Eric's damsite.
The record so far was 19 Kings each side, and around 900 ply (which is already impressive).
I'm afraid that (at least) my computer program (as is) could not retrieve the 20 king x 20 king.
But it would be a computer challenge to find a faster solution!

But anyway, for non kings on the black side I think 5 white kings is the maximums for a 20 piece x 20 man position, (if there are no flaws in my program), and to be honest that was a little surprise to me.

Bert

[BertTuyt]

I tried to get a better approximation (and understanding) for the "practical" size of the Draughts state-space.
Herewith the first results for the equal man positions.
In the graph I also plotted the maximum number of positions based on combinatorial analysis (which I shared also in the past).
This first graph is based on 100M simulations, which I want to increase towards 1G.

Part of the "practical" positions could still be illegal, and I hope to find more "practical" position design rules, so the numbers I found could be reduced further.
In this graph the maximum number log(number of positions) is still around 13.5 (number of man each side 11- 14).
As this is the first run, I want to do somewhat more testing, to make sure these numbers are valid (and/or make sense)...
Also worth mentioning is that all positions included in this count are quiet, so no capture possibility for white/black.

Think also Michel found a number somewhere between 10^12 and 10^13......

Bert

[MichelG]

I tried to get a better approximation (and understanding) for the "practical" size of the Draughts state-space.
Herewith the first results for the equal man positions.
In the graph I also plotted the maximum number of positions based on combinatorial analysis (which I shared also in the past).
This first graph is based on 100M simulations, which I want to increase towards 1G.

Part of the "practical" positions could still be illegal, and I hope to find more "practical" position design rules, so the numbers I found could be reduced further.
In this graph the maximum number log(number of positions) is still around 13.5 (number of man each side 11- 14).
As this is the first run, I want to do somewhat more testing, to make sure these numbers are valid (and/or make sense)...
Also worth mentioning is that all positions included in this count are quiet, so no capture possibility for white/black.

Think also Michel found a number somewhere between 10^12 and 10^13......

Bert

I am still not very clear on what number exactly you mean by the number of 'practical' positions. I can think of a few definitions:
1) The number of positions that can be reached if both players cooperate. These include all the positions that can be reached theorically, like the 20x20 kings position.
2) The number positions that occur frequently in gameplay. (with some definition of 'frequently')
3) The proof-tree of draughts; the minimum number of positions to store that proves draughts to be a draw.

I have done extensive research on the following question: can you create a precomputed table of midgame positions so big that it will significantly enhance the gameplay of a draughts engine? This question mostly resembles definition 2.

My answer to that is: no, not with the current hardware available to amateurs. But you can if you have access to a massive computer resources, for example a supercomputer.

Michel

[BertTuyt]

Michel, you are right that "practical" needs to be defined in a better way.
I also applied a definition like your definition 2.

2) The number positions that occur frequently in gameplay. (with some definition of 'frequently'

The numbers presented in the graph are based on frequent-like positions.

Also my conclusion so far is that a mid game table seems to be feasible for a supercomputer setup already today, but not for the hardware resources available to amateurs.

Bert

[BertTuyt]

When you generate a random positions with many pieces, the chance is huge that the position is non static (with a potential capture for white or black).
To better quantify this number I measured the number of random simulations required to yield 1000 positions (with only man, and number of white man equals black man) with white to move, and both white and black do not have a capture.
See the results in below table.

Code: Select all

1	1072
2	1337
3	1890
4	3362
5	6382
6	14028
7	33864
8	84357
9	218556
10	606656
11	1677279
12	4058450
13	9599712
14	20177119
15	35620544
16	51238889
17	61743616
18	57001703
19	35567900
20	14922406

So as an example , you need to run 4058450 simulations, to create 1000 static positions with white and black both having 12 man.
When you exclude these positions from the maximum (keep in mind that this maximum also includes illegal positions, and legal positions which require much cooperation from both sides involved) you get the next graph (if I didn't make some mistakes), which shows the number of man for each side on the horizontal axis, and on the vertical axis the log of the static positions.

And to phrase the wording of Michel, unfortunately still supercomputer territory...

Bert

[MichelG]

Michel, you are right that "practical" needs to be defined in a better way.
I also applied a definition like your definition 2.
The numbers presented in the graph are based on frequent-like positions.

Also my conclusion so far is that a mid game table seems to be feasible for a supercomputer setup already today, but not for the hardware resources available to amateurs.

I have found the following empirical formula for question 2:

For a database consisting of the N most frequently occurring practical positions, the chance p that another random practical position is in this database can be approximated by the following formula:

p = 1 - exp(-c*sqrt(N))

with c some constant.

e.g. with a small database (where small means something like 10^12 positions) you can get a certain percentage for p. But if you want p to be closer to 1, things very quickly become exponentially harder. This formula at least seems to work for small N

In any case, you can't really say that a database of size N encompasses all practical positions; there will always be large numbers of frequent position that are not in the database.
Michel

[BertTuyt]

Slightly off topic

But for those who want to upgrade to a new computer, wait for the next 8-core Intel processor...

Apart from the new Devil’s Canyon processor, Intel has also announced yet another enthusiast-oriented processor at the on-going Game Developers Conference. Part of the company’s long running Extreme Edition high-end processors, this upcoming Intel Core i7 Extreme Edition processor is Intel’s first 8-core, 16-thread desktop processor and based on CPU architecture called Haswell-E.

As a comparison, the current top of the range Intel Core i7 Extreme Edition processor – the Core i7-4960X which is based on Ivy Bridge-E architecture – comes with 6 CPU cores and 12 CPU threads.

Apart from packing plenty of processing power, it will also be supported by a new chipset named Intel X99 and together, they will become one of the first desktop platform to support the equally new DDR4 memory.

While the new 8-core Intel Core i7 Extreme Edition processor will be released sometime in the second half of the year, Intel didn’t provide detailed information regarding it at the time this article is written. We will continue to keep you in the loop once Intel churned out more information for us to convey to all of our readers here.

Bert