Author |
Topic: Reusing information (Read 826 times) |
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender: 
Posts: 138
|
 |
Reusing information
« on: Mar 21st, 2006, 4:41am » |
 Quote  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)
 
Gender:
Posts: 1413
|
|
Re: Reusing information
« Reply #1 on: Mar 21st, 2006, 4:52am » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Reusing information
« Reply #2 on: Mar 21st, 2006, 2:25pm » |
Quote 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:
Posts: 405
|
|
Re: Reusing information
« Reply #3 on: Mar 22nd, 2006, 12:45am » |
Quote 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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print