Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Preserving hashtable information?
        
(Message started by: unic on May 8^th, 2006, 11:19am)

Title: Preserving hashtable information?
Post by unic on May 8^th, 2006, 11:19am

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?

Title: Re: Preserving hashtable information?
Post by jdb on May 8^th, 2006, 2:45pm

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.

Title: Re: Preserving hashtable information?
Post by Fritzlein on May 9^th, 2006, 6:09pm

on 05/08/06 at 14:45:49, 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?

Title: Re: Preserving hashtable information?
Post by chessandgo on May 9^th, 2006, 6:36pm

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 ;)

Title: Re: Preserving hashtable information?
Post by Swynndla on May 11^th, 2006, 10:30pm

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.

Title: Re: Preserving hashtable information?
Post by unic on May 13^th, 2006, 7:43pm

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.

Title: Re: Preserving hashtable information?
Post by aaaa on Apr 6^th, 2008, 1:39pm

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.

Title: Re: Preserving hashtable information?
Post by Janzert on Apr 6^th, 2008, 11:22pm

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

Title: Re: Preserving hashtable information?
Post by IdahoEv on Apr 7^th, 2008, 12:37pm

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.

Title: Re: Preserving hashtable information?
Post by aaaa on Apr 7^th, 2008, 1:09pm

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.

Title: Re: Preserving hashtable information?
Post by Janzert on Apr 7^th, 2008, 2:15pm

on 04/07/08 at 12:37:09, 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

Title: Re: Preserving hashtable information?
Post by Fritzlein on Apr 7^th, 2008, 2:17pm

on 04/07/08 at 12:37:09, 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.

Title: Re: Preserving hashtable information?
Post by IdahoEv on Apr 9^th, 2008, 1:30pm

on 04/07/08 at 14:17:56, Fritzlein wrote:

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.