Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 4:29am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Reusing information »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Reusing information
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Reusing information  (Read 799 times)
Ryan_Cable
Forum Guru
*****



Arimaa player #951

   


Gender: male
Posts: 138
Reusing information
« on: Mar 21st, 2006, 4:41am »
Quote Quote Modify Modify

In a single turn, the vast majority of pieces do not move.  Often 2 or 3 quadrants are totally unchanged.  Most times, most pieces will have the same available moves they had on the last turn, and the effect of making most of those moves will usually be about the same.  Humans naturally use this fact to let them focus their thoughts on where the action is.  I think it should be possible to make a bot take some advantage of this as well.
 
For example, if on move Nb silver spends all 4 steps moving within the Northeast, then the relative change in evaluation of a gold move that spends all 4 steps moving within the Southwest is likely to be almost the same on N+1w as it was on Nw.  Moreover the best move that spends all 4 steps moving within the Southwest is likely to be the same on N+1w as on Nw.
 
To me, this suggests that it would be useful to create hash tables for each quadrant.  If nothing changed within a quadrant and within the squares immediately neighboring the quadrant then you could look up the value of the best possible move that is contained entirely within that quadrant.  I'm not sure how this would work within the step based search that bots use, but I'm pretty sure something similar could be done.
 
I can think of a few cases where moves outside the quadrant and its neighboring squares will substantially change the value of a move, but if the time savings were large enough these could be detected on a case by case basis.  Even if I am on the wrong track with the idea of quadrant hash tables, it seems that in many cases there should be some way to make evaluating the relative change of a step or a move more efficient than evaluating the entire resulting position.
 
PS  Roughly how many operations does it take to evaluate a position?  How many operations does it take to do a static goal/trap search?
IP Logged
99of9
Forum Guru
*****




Gnobby's creator (player #314)

  toby_hudson  


Gender: male
Posts: 1413
Re: Reusing information
« Reply #1 on: Mar 21st, 2006, 4:52am »
Quote Quote Modify Modify

Yes, I want to explore an avenue similar to this.  My version is a little less ambitious - just break up the eval into 4 separate evals that add up.  Therefore if a quadrant config had ever been seen before, it could simply be looked up.  Any global eval terms would then have to be added in (eg total number of rabbits left).
 
Your ideas look harder to implement - but I'm not really an expert programmer.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Reusing information
« Reply #2 on: Mar 21st, 2006, 2:25pm »
Quote Quote Modify Modify

Local evaluation is an interesting idea: I understand it is extremely important in the game of go.  However, in go the moves in one sector of the board influence the strength or weakness of the players' positions elsewhere in ways that are extremely difficult to evaluate.  I suspect the same will be true for Arimaa.  For example, JDB and I spent lots of time evaluating a race game in which it would have made a world of difference for the f6 quadrant for the silver elephant to be on d3 rather than b3 in the quadrant diagonally across.
 
I'm quite curious to hear what this does for Gnobot, 99of9, and I hope you get a chance to implement it so that we can see.  Too bad that darn Postal Tournament takes up so much time.
 
P.S. If anyone gets a chance, ask Fotland about local evaluation in go, and report back with his insights.
IP Logged

IdahoEv
Forum Guru
*****



Arimaa player #1753

   


Gender: male
Posts: 405
Re: Reusing information
« Reply #3 on: Mar 22nd, 2006, 12:45am »
Quote Quote Modify Modify

I've thought quite a bit about this as well.   I've considered a number of different neural network approaches to board evaluation.   In one of them, the first layer would be a cluster of neurons for each piece, rather than for each location; that cluster would present a set of outputs that encoded the piece's general disposition based on its surroundings.   A second layer would integrate the outputs from each piece, along with their location, into an evaluation of board quality.
 
If done that way, then when evaluating a new board position only those pieces that have seen position change within their event horizon need to recompute their networks; others can just reuse their values from the previous board.   Given that an ANN like this is likely to be vastly slower than bit-shifts on bitboards, such optimization would probably be extremely important.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.