BertTuyt wrote:.
I started now with the 7 piece database and i generated the 5Kx2K and 2Kx5K. But when i want to built other ones i get memory issues for 2 reasons, total memory when all sub-databases is loaded is larger then my memory space and even some single initial databases (not yet compressed) grow beyond my memory space and Windows XP.
When moving to Windows XP-64 (or a Vista alternative) only partly solves the issue. When database access is via memory-mapped file on Hard-Disk, i assume the access time will become so slow that the database calculation time will explode due to the I/O bottleneck.
I know that Michael has generated 7-piece databases based on slices (so a database is characterized by example a piece on the most advanced rank). This solves some of the issues, but the program becomes really complicated, and the number of databases also become very large.
Bert
Bert, I built all my databases using machines running 32-bit Windows and 2gb of RAM. I solved both the size and the parallelism problems by using a more complicated indexing function. There is a paper on my web site that describes how this works for building the 10pc English db. Link:http://pages.prodigy.net/eyg/Checkers/10-pieceBuild.htm I used the same indexing to build the 10x10 db. Actually its the same code, I just replaced the move generator.
I do not use memory mapped files, because they seem to give no control over the caching. The subdivisions being built are small enough to fit entirely in RAM (because of the indexing), and the lookups on the dependency subdivisions during the IO passes of the build are managed using an LRU cache.
I thought about this concept myself, but I had the idea that due to the big addrees space it would be comsuming too much space.
One question, why don't you look up the black on move positions in the mirror position with white on move??
Kind regards,
Feike Boomstra
What do you mean by mirror position ?
In the examples I gave (1king and 3 men against 2 kings, or 5 kings against 2 kings) I do not see any mirror position.
Gérard
Gerard, do you already start generating databases based on the idea that (for example) most positions are a draw.
Or do you generate the databases in a "normal" way (Grimminck/Jetten approach), but based on the database content (such as majority win , draw, or whatever), change the way it is stored on HD/Memory?
BertTuyt wrote:Gerard, do you already start generating databases based on the idea that (for example) most positions are a draw.
Or do you generate the databases in a "normal" way (Grimminck/Jetten approach), but based on the database content (such as majority win , draw, or whatever), change the way it is stored on HD/Memory?
Bert
Bert,
What do you mean by "normal" way (I am not aware of Grimminck/Jetten approach).
For the 2-6 endgame database I guess it is a similar approach except for the storage process.
For the 7-pieces database my idea was really to use Ed. approach for the very unusual (unuseful?) configurations.
Gérard
Gerard, with a normal way i mean when you store initially all positions during Database generation (WDL information).
Later you can then decide to use a alternative storage method based on the Database content.
In the case of Grimminck/Jetten all postions are stored and retrieved via an index function.
In a second phase the dynamic postions (white must "kill" a black piece) are deleted, and therefore compression could be optimized.
BertTuyt wrote:Gerard, with a normal way i mean when you store initially all positions during Database generation (WDL information).
Later you can then decide to use a alternative storage method based on the Database content.
In the case of Grimminck/Jetten all postions are stored and retrieved via an index function.
In a second phase the dynamic postions (white must "kill" a black piece) are deleted, and therefore compression could be optimized.
Bert
Bert,
I made the generation process with the common slice approach. Let's take for example the positions with 4kings+1man againts 2kings. I first generated in a "normal" way the database with the white man on square 6, then I used my storage process so I can forgot all the "normal" information generated before continuing the generation process by putting the white man on sqaure 7 etc.
Is that answer your question ?
Gérard
Gerard, yes i think I do understand.
Do you, by the way, participate in the Computer Games Olympics, next week?
As I travel monday to the USA (work), I cant be there.
So hope from the US to react on some postings here, if time allows.
Also cant wait to start with some ideas presented here.
On the other hand , I have a detailed list with improvement topics for my new Damage Engine, which come first.
Im now working on Breakthrough patterns, which is an interesting topic in it self.
After that I have to start with parallel multi-core processing (but im still waiting on the new Intel Penryn or AMD Barcelona processor , later this year).
BertTuyt wrote:Gerard, yes i think I do understand.
Do you, by the way, participate in the Computer Games Olympics, next week?
As I travel monday to the USA (work), I cant be there.
So hope from the US to react on some postings here, if time allows.
Also cant wait to start with some ideas presented here.
On the other hand , I have a detailed list with improvement topics for my new Damage Engine, which come first.
Im now working on Breakthrough patterns, which is an interesting topic in it self.
After that I have to start with parallel multi-core processing (but im still waiting on the new Intel Penryn or AMD Barcelona processor , later this year).
Bert
Bert,
No I will not participate in the Computer Games Olympics next week. During the computer french open championship your dutch collegues told me that they will be very happy if I could particpate to the next Culemborg tournment, organised at the end of the year. So I will prepare Damy for this event and I looking forward to seeing you also at this event.
I am just finshing a very new version of Damy working with parallel 2-core processing. After a necessary test period my intention is then to come back and improve my evaluation function.
Can you tell me what you mean by "Breakthrough patterns" because it sounds like what I already made.
Gérard
I thought about this concept myself, but I had the idea that due to the big addrees space it would be comsuming too much space.
One question, why don't you look up the black on move positions in the mirror position with white on move??
Kind regards,
Feike Boomstra
What do you mean by mirror position ?
In the examples I gave (1king and 3 men against 2 kings, or 5 kings against 2 kings) I do not see any mirror position.
Gérard
OK, I see. You have only one database/slice for e.g. 1 king, 3 men vs. 2 kings and you have entries for majority on move and minority on move.
I in the past used a complicated function to determine if white could break through the black defence and promote a man to a king.
But this function mostly dealt with testing if 1 man could promote.
A combination of white and black man was to difficult to implement in "if the else" statements.
These days with large memory and faster processors it is possible to store all combinations for white and black man in a file, and for every combination i do a tree-search to see if white can promote.
In these positions white must move and black is allowed to make a NULL-move ( as i assume that there are more man on the board elsewhere).
Im now testing a file with around 60M positions for white to move.
Positions 1 - 5 and 16 - 20 are black or empty.
Positions 6 - 15 are black/empty/white.
This yields a total of ( 2 ^ 10 ) * ( 3 ^ 10 ), is around 60M.
In the database i store a byte for every position to determine static/dynamic, and the nr. ply to get to a promotion.
Compressed this is ca. 1M (zip compression), so if i apply my own compression is will become somewhat larger.
If after testing is works (i normally do extensive tests for months, before i go to a tournament), i will implement larger databases for breakthrough.
In the end i expect to have a file yielding around 15 * 10^9 positions
( 2^10 ) * ( 3 ^15 ) , so positions 1 - 25. Also i will generate a file for black to move and white to move separately.
The black breakthrough is calculated with the same database but with another indexing function.
Guess you have a similar approach.
But nevertheless im interested in your numbers.
Concerning speed, Damage now calculated 1M nodes/sec (= 500K evaluations/sec) on a AMD 3200.
I think that with a Quad Core Penryn and/or Barcelona, I will reach 5M Nodes/sec.
Bert,
Now I understand what you mean by "break through " but something looks strange for me. You seem to look for a breakthrough only by consering white men on 6-15.
Does that mean that you use classical "if then else" approach to find a breakthrough in very common situation like white 19 and 20 against black 9 and 3 ?
Concerning speed can you formulate your question more precisely ?
I imagine at least 3 figures :
1) The number of generated positions
2) The number of "really" evaluated positions
3) the number of position evaluated via a hash table
Even with this formulation it is not that clear : when you encounter a position already seen (you classicaly find the position in a hash table) do you increment the number of generated position and/or the number of evaluated position ?
In addition in a bi-processor environnement it happens also that it is difficult to avoid that the 2 processors evaluates the same positions but I am not able to have the figure for these cases.
It is easy for me to add some new counters in my program in order to have the correct figure you ask for but I need first to know what do you really would like to measure.
Gérard
good questions !
In the case of Damage the 1 Mnodes/sec is the number the Movegenerator is called every second.
500K/s is the number the real evaluation function is called / second.
I don't count in these number the situation where a hash-table entry already provides a cut-off.
In my present breakthrough function i only use "if-then-else" statements.
In the table im generating now i only have white man on 6-15, no additional if-then-else statements. So in case a man on 16-20 is positioned, it will not been seen, and also will not be included in the breakthrough decision.
If all works I will extend the table , and white man will also be included on positions 16-20.
If you have any suggestions, food for though, or whatever, please let me know.
My old computer went down, and I had to buy a new one. I took a pentium d915.
Due to reasons of free Intel software on Linux, I went to Fedora 64 bits.
With a single processor I reached 700.000 nodes/sec. (If I look at your numbers I have still work to do.) The disappointing thing however was that going parallel, the number of nodes/sec nearly doubled, but it is not very effective. The throughput time for calculating a move (with the same depth) is increased, but not doubled, more around 30 - 40 %. I think a lot of activity is useless, because the other thread already reached a conclusion and you throw away the still running thread.
I am very interested in other user multi processor experiences.
I used the Intel c++ compiler with the omp directives.
kind regards, have a good trip to the States,
Feike Boomstra
My computer is a laptop with a core 2 CPU T7200 2GHz.
When using only one processors the figures are :
Number of generated positions/s : 1 500 000
Number of evaluated positions/s : 700 000
Of course I suspect this last number will decrease when I will improve my evaluation function
Gérard
good questions !
In the case of Damage the 1 Mnodes/sec is the number the Movegenerator is called every second.
500K/s is the number the real evaluation function is called / second.
I don't count in these number the situation where a hash-table entry already provides a cut-off.
In my present breakthrough function i only use "if-then-else" statements.
In the table im generating now i only have white man on 6-15, no additional if-then-else statements. So in case a man on 16-20 is positioned, it will not been seen, and also will not be included in the breakthrough decision.
If all works I will extend the table , and white man will also be included on positions 16-20.
If you have any suggestions, food for though, or whatever, please let me know.
Bert
Bert,
By reading again your above post I have a doubt concerning the number of generated positions.
In the initial position when I call ONE time the movegenerator it generates NINE poisitions.
Do you count ONE or do you count NINE in your global figure ?
Gérard
