Author |
Topic: Preserving hashtable information? (Read 2220 times) |
|
unic
Forum Guru
Arimaa player #1878
Gender: 
Posts: 63
|
 |
Preserving hashtable information?
« on: May 8th, 2006, 11:19am » |
 Quote  Modify
|
I'd like to preserve hashtable information from move to move. However, as the perl script starts a new, fresh instance of the getMove program each time it is the bot's turn, I am not sure how this could be done (without kludgy solutions like saving the whole hashtable to the harddrive).
How do other bot developers do this?
Or do the bots in generally start each move with an empty hashtable and no saved information?
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Preserving hashtable information?
« Reply #1 on: May 8th, 2006, 2:45pm » |
Quote Modify
|
It is likely possible to modify the bot perl script to allow the bot to stay running. However, I have no idea about perl whatsoever.
It would be nice to not have to restart after each move, but in the end it likely doesn't make much difference.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Preserving hashtable information?
« Reply #2 on: May 9th, 2006, 6:09pm » |
Quote Modify
|
on May 8th, 2006, 2:45pm, jdb wrote:| It would be nice to not have to restart after each move, but in the end it likely doesn't make much difference. |
|
My first thought was that, with a branching factor of 15,000 per turn, only a tiny fraction of the search space would be re-used, so little that it hardly matters.
But then it occurred to me: what if the opponent undoes your move? You could then re-use almost the entire hash table, couldn't you, and deepen your previous search?
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Preserving hashtable information?
« Reply #3 on: May 9th, 2006, 6:36pm » |
Quote Modify
|
wow, it kills my last wishes to finish my bot  ... I counted very much on preserving things from one move to another ... thanks for pointing it out unic !
and without ability to kibbitz, arimaa and the world look pointless to me now ...  
so sad 
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Preserving hashtable information?
« Reply #4 on: May 11th, 2006, 10:30pm » |
Quote Modify
|
In the Bot Interface Kit, the README.gamestate file begins with Quote:You really don't need to use the info in the gamestate
file, until you get to the point of wanting to allow
your bot to think while it is the opponents turn,
taking into consideration how much time there is left
in the game, automatically handle takeback requests
and other such things. |
|
So I think it's possible to change your bot to keep running between moves.
The danger of modifying the perl interface script is that during the bot world champs, you'll lose that functionality.
Or that's how it seems to me anyways.
|
| « Last Edit: May 11th, 2006, 10:37pm by Swynndla » |
IP Logged |
|
|
|
unic
Forum Guru
Arimaa player #1878
Gender:
Posts: 63
|
|
Re: Preserving hashtable information?
« Reply #5 on: May 13th, 2006, 7:43pm » |
Quote Modify
|
Been thinking about this a bit more... perhaps have the program called by the script just be an intermediary, which communicates via files with the main gameplaying program. That way, one could do pondering, and preserve information... all one would need to do would be to occasionally poll the existence of the communication files. (This is vaguely similar to the file communication which the Othello program Edax uses - see http://abulmo.club.fr/edax/edax.htm#filesystem for details.)
Still not sure if it's worth the trouble to implement this... but pondering would certainly be useful as well. An idea to bear in mind for the future.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Preserving hashtable information?
« Reply #6 on: Apr 6th, 2008, 1:39pm » |
Quote Modify
|
Has anyone succeeded in (efficiently) preserving data between getMove calls yet? I ask this because I haven't familiarized myself with the interface yet, but if the possibility of data retention is significantly crippled, then this would be an unnecessarily restriction of bot potential and therefore an unfair state of affairs with respect to the Challenge, meaning a change in interface would be in order.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Preserving hashtable information?
« Reply #7 on: Apr 6th, 2008, 11:22pm » |
Quote Modify
|
OpFor uses a custom interface script that keeps the bot running for the full length of the game. Once the postal mixer is up and running and I have a chance to clean the script up a bit I hope to release it and a sample bot using it for general use. I also hope to complete a GUI client for opfor this year. But (a) I hate GUI programming, which leads to (b) I'm really horrible at GUI programming, so I don't know how far that will get.
Janzert
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Preserving hashtable information?
« Reply #8 on: Apr 7th, 2008, 12:37pm » |
Quote Modify
|
This could certainly be done.
But I have strong doubts about the usefulness of maintaining the hash from one turn to the next. Most bots will fill up even a large hashtable in the first minute of a search. The majority of those states in the table will be in ply 2 of the current search, which is your opponent's potential replies.
After your opponent's reply, most of those states are obsolete. If you started the new search with that table, you'd have very few hashtable hits, plus your table would start off full so you wouldn't be able to store new states. So all the new states relevant to your current search would end up not getting hashed, and you'd have to eval lots of them repeatedly.
You could maybe make it worthwhile if you had some sort of very fast hashtable management that remembered the last time you accessed certain states and expired the old ones to make room for new positions. But I worry about how much time it would take to maintain that ... wouldn't you have to keep a sorted index to the table, sorted by "last access time"? I would think the time required to do that would negate the value of persisting your hash.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Preserving hashtable information?
« Reply #9 on: Apr 7th, 2008, 1:09pm » |
Quote Modify
|
It seems to me, that an obvious benefit of preserving the state of a bot between moves would be, that for the purpose of detecting repetitions, one wouldn't need to parse past moves over and over again.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Preserving hashtable information?
« Reply #10 on: Apr 7th, 2008, 2:15pm » |
Quote Modify
|
on Apr 7th, 2008, 12:37pm, IdahoEv wrote:
After your opponent's reply, most of those states are obsolete. If you started the new search with that table, you'd have very few hashtable hits, plus your table would start off full so you wouldn't be able to store new states. So all the new states relevant to your current search would end up not getting hashed, and you'd have to eval lots of them repeatedly.
You could maybe make it worthwhile if you had some sort of very fast hashtable management that remembered the last time you accessed certain states and expired the old ones to make room for new positions. But I worry about how much time it would take to maintain that ... wouldn't you have to keep a sorted index to the table, sorted by "last access time"? I would think the time required to do that would negate the value of persisting your hash. |
|
OpFor uses what I believe is a fairly standard scheme to handle this. Every entry has an "aged" field that indicates whether the entry is old. This is set for all entries at the end of a move and then cleared when an entry is used during the search. Entries in the hash table are replaced if they are aged or the new entry has been searched to a greater depth. Also up to 4 slots in the hashtable are probed in a lookup.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Preserving hashtable information?
« Reply #11 on: Apr 7th, 2008, 2:17pm » |
Quote Modify
|
on Apr 7th, 2008, 12:37pm, IdahoEv wrote:| But I have strong doubts about the usefulness of maintaining the hash from one turn to the next. Most bots will fill up even a large hashtable in the first minute of a search. The majority of those states in the table will be in ply 2 of the current search, which is your opponent's potential replies. |
|
This doesn't sound so bad. You know the move you sent, so while you ponder during his think time, ply 2 is your responses to your opponent's possible moves, right? So it should have more than zero value. But I guess even so only 1/15000 of the entries will be useful.
|
| « Last Edit: Apr 7th, 2008, 2:27pm by Fritzlein » |
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Preserving hashtable information?
« Reply #12 on: Apr 9th, 2008, 1:30pm » |
Quote Modify
|
on Apr 7th, 2008, 2:17pm, Fritzlein wrote:
This doesn't sound so bad. You know the move you sent, so while you ponder during his think time, ply 2 is your responses to your opponent's possible moves, right? So it should have more than zero value. But I guess even so only 1/15000 of the entries will be useful. |
|
It wasn't clear to me that the thread was talking about pondering. So I was assuming we were talking about persisting hashtable from my move to my next move - a jump of 2 ply. At that point your hashtable is pretty much useless.
With pondering, though, it's a different matter.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print