Author |
Topic: Multiple core and non-locking transposition tables (Read 4685 times) |
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
 |
Re: Multiple core and non-locking transposition ta
« Reply #15 on: Aug 29th, 2010, 6:32pm » |
 Quote  Modify
|
on Aug 29th, 2010, 6:30pm, speek wrote:
Well, 10% is a hefty percentage for one low-level operation like doing a put to a hash table. It would certainly be the kind of cost I'm talking about. |
|
Reading and writing to a huge hash table which doesn't fit in the cache necessarily means accessing RAM most of the time. It takes many CPU cycles to access RAM.
For me it was definitely worth it to add the transposition table.
|
|
 IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Multiple core and non-locking transposition ta
« Reply #16 on: Aug 29th, 2010, 6:56pm » |
Quote Modify
|
on Aug 29th, 2010, 6:16pm, rbarreira wrote:
I'm not sure if that's what you mean, but I think the better way is to xor the key and the data to get the key which will be stored. |
|
Sorry, yeah that's what I meant.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Multiple core and non-locking transposition ta
« Reply #17 on: Aug 29th, 2010, 10:13pm » |
Quote Modify
|
on Aug 29th, 2010, 6:26pm, speek wrote:| Well, I don't understand your example of an opponent making a "fixed" move (what is that?) and 8 independent steps. The first 4 independent steps resulting in position A will be in my set of unique moves once. Then, the opponent has a "fixed" move. Then I do 4 more moves independent of each other and the one move I started with. How am I duplicating positions? |
|
OK, for illustration suppose the gold pieces are all on the second and third ranks, with the silver pieces all on the sixth and seventh ranks, with Gold to move. The position I have in mind three ply from now has all of Gold's third-rank pieces advanced one step to the fourth rank (eight independent steps) and Silver's four central pieces advanced one step each to the fifth rank (the opponent's "fixed" reply). On the way to this position three-ply deep, you can make 70 different moves at the root of the search, as there are 70 different ways to step four of your front pieces foward. The opponent responds the same way in each case, and then you move the other four pieces forward. Your duplicate move detection doesn't eliminate these different ways of arriving at the same position, as all the root moves are different.
Does this clarify what duplicate-position detection can do that duplicate-move detection can't do?
|
|
IP Logged |
|
|
|
tize
Forum Guru
Arimaa player #3121
Gender:
Posts: 118
|
|
Re: Multiple core and non-locking transposition ta
« Reply #18 on: Aug 30th, 2010, 12:03am » |
Quote Modify
|
I was clearly wrong about that most used lock-less hashing...
on Aug 29th, 2010, 10:15am, doublep wrote:| Plain non-locking hashing is really not an option, because it can yield not just a wrong move/score when two threads read/write the same entry, but something illegal and crash your program. |
|
To fix that problem you don't have to lock the hash, just validate that the move is a legal one, even with a lock I wouldn't trust the move without validation but maybe I'm just paranoid. 
on Aug 29th, 2010, 5:33pm, speek wrote:| I understand this, I'm just dubious of it's value for Arimaa. Firstly, these differences mean you can't use it to generate a correct collection of unique moves for a given position - that can't be a fuzzy operation. It also does have to be cleared (though not necessarily reallocated) each time. |
|
First you should never clear the hash other than when it's being initialized, instead use an age counter or something similar if you would like to know if the entry is from a previous iteration.
In marwin I also use a hash that filters away dublicates inside of a move, in fact the 2010 version doesn't have any transposition table. I have now added such a table and it helps, on p2 searches it's mostly in the 0-30% range, but on a 2 minutes search it usually searches one step deeper. Not earth shattering but a nice improvement.
on Aug 29th, 2010, 6:21am, rbarreira wrote:| For me, the solution was to use Hyatt's lockless hashing: |
|
Nice I will use that too.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Multiple core and non-locking transposition ta
« Reply #19 on: Aug 30th, 2010, 8:26am » |
Quote Modify
|
While on the topic of transposition tables, has anyone ever considered persisting some entries on-disk for future games? As to not add overhead it could be implemented in a manner such that between turns or at end of game, the deepest or most seen entries could be written to an on-disk transposition table, which could then be used to either initialize or supplement the normal one in subsequent matches.
Recently I ran some processing on games since the start of this year and found that out of 983873 turns, there were 946219 unique positions (mirror images counting as duplicate). Since I'm sure most of the duplicates are very early game, I don't think the on-disk table would have that big an impact overall, but I wonder if it could be worth it for perhaps getting slightly more depth in the first few turns. I mean.... surely out of all the times double-99of9 opening is seen, it could be searched slightly deeper by re-using information found in past games.
|
| « Last Edit: Aug 30th, 2010, 8:27am by Rednaxela » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Multiple core and non-locking transposition ta
« Reply #20 on: Aug 30th, 2010, 9:00am » |
Quote Modify
|
The problem with persistent knowledge is that it would have to be recalculated every time you change your evaluation function or even much of the search code. But it could be worth it for a quite mature bot (I'm guessing none or very few of the existing Arimaa bots can really be called mature yet).
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Multiple core and non-locking transposition ta
« Reply #21 on: Aug 30th, 2010, 9:54am » |
Quote Modify
|
on Aug 29th, 2010, 10:13pm, Fritzlein wrote:
Does this clarify what duplicate-position detection can do that duplicate-move detection can't do? |
|
Thanks Fritz, yes, I understand now. I'll have to try not clearing my unique move hash and see what effect it has.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Multiple core and non-locking transposition ta
« Reply #22 on: Aug 30th, 2010, 7:51pm » |
Quote Modify
|
on Aug 30th, 2010, 12:03am, tize wrote:| In marwin I also use a hash that filters away dublicates inside of a move, in fact the 2010 version doesn't have any transposition table. I have now added such a table and it helps, on p2 searches it's mostly in the 0-30% range, but on a 2 minutes search it usually searches one step deeper. Not earth shattering but a nice improvement. |
|
Thanks for the practical results, tize. That's much more informative that my speculation about duplicate positions. You say that searching one step deeper isn't earth-shattering, but isn't that equivalent to searching more than three times as fast? I'm trying to think what other optimizations (other than alpha-beta pruning) result in an additional step of depth in a two-minute search in an already-strong bot.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Multiple core and non-locking transposition ta
« Reply #23 on: Aug 31st, 2010, 8:57pm » |
Quote Modify
|
on Aug 30th, 2010, 9:00am, rbarreira wrote:| The problem with persistent knowledge is that it would have to be recalculated every time you change your evaluation function or even much of the search code. But it could be worth it for a quite mature bot (I'm guessing none or very few of the existing Arimaa bots can really be called mature yet). |
|
Well as far as numerical score values or bounds, yes, that data does get broken when changing the bot, however I have a feeling that the best/refutation moves are still of significant value. Even after changing the evaluation function drastically, chances are the best/refutation move from an old eval function is still a good first guess when searching. This could work simply by including a "bot revision" field in the on-disk transposition table data.
Today as I was pondering parallel searches... and I think I realized one possible optimization for the parallel alpha-beta search, that applies best in multiple-steps-per-turn situations like with Arimaa. During any given turn from a given starting position, the resulting value of alpha will always end up being the greatest alpha found in the 4-step tree of that turn. Due to that, perhaps it would be advantageous to use a "shared alpha" within each subtree for a turn. Normally some parallel branches would start with non-optimal alpha values thus leading to more visited nodes than a non-parallel implementation, limiting the scalability. Using a "shared alpha" as I describe should bring the visited nodes of the parallel search back to something close to the non-parallel search, thus improving the scaling.
Now, implementing the "shared alpha" with traditional locking would probably have too much overhead, however it could be implemented very efficiently by making use of atomic compare-and-set/swap instructions. In Java this would be implemented pretty easily by using the AtomicInteger class for the shared alpha. In C/C++ this could be implemented by careful use of a "volatile int *" along with the compare-and-swap instruction.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print