Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> A new way to think about the Arimaa board?
        
(Message started by: IdahoEv on Jan 15^th, 2007, 7:32pm)

Title: A new way to think about the Arimaa board?
Post by IdahoEv on Jan 15^th, 2007, 7:32pm

I had this thought in the shower yesterday; a different perspective for analyzing the Arimaa board and how it might be applied to AI.

Defining "true distance"
Given a certain target square and a piece in another location, consider the question of how "far away" the piece is from reaching that square. For example, I may have as an eval goal: make certain that your elephant is always at least four steps away from my camel. To really evaluate that goal accurately, I need a measure of distance I can compare with the criterion "four steps".

Obivously, that measure of distance is more than just the number of intervening squares. If there's a friendly piece in the way, I have to move it, adding a step. If there's an undefended trap in the way, I have to go around. If there's an enemy in the way, I have to expend a step pushing them out of the way ... unless they are my size or bigger, in which case I have to go around, maybe even moving additional pieces up to keep me unfrozen.

If I have to move additional pieces to make my move possible, the move cost from A to B for some piece is then the step count of its own moves between those points plus (recursively) the sum of all necessary support moves to make that possible.

Equivalence to solving Arimaa
Taken to the extreme with all possible support moves figured in, this becomes another entire way to analyze the game of Arimaa. The answer to the question "what is the true distance of the minimum route for gold and/or silver's rabbit to the goal", is equivalent to the solution to Arimaa (neglecting immobility wins): the color whose "true distance" rabbit-goal is smaller is the winner. If the answer is infinite, the game is a draw.

Obviously we can't accomplish that full calculation and use this approach to solve Arimaa, but it's a way to demonstrate that this analysis is at least hypothetically complete.

Estimating move costs to improve static evaluation
The two critical questions about this "true distance" thing for me are:
1. Is it possible to generate a fast estimate of the travel distances that only includes the first and/or second order of interactions?
2. Would this set of estimates be sufficiently useful in improving static evaluation to be worth the cost of computing them?

So here's a thought experiment for how a bot might accomplish this. Given a certain piece type (say, gold dogs), make an 8x8 array representing the approximate move cost associated with each square. Fill each square with a small integer thus:

1 for an empty square because it will cost one step to move through it.
2 if occupied by a friendly and an adjoining square is empty. (move it away to allow passage)
2 if occupied by a smaller enemy and an adjoining square is empty (1 extra step to push them away).
infinite if totally filled & surrounded (nowhere to go)
infinite for an undefended trap (i would die)
infinite if it contains an equal or larger enemy (can't push it)
adjoined by a larger enemy but no friendlies. (i'd get frozen)

You'd have to generate twelve such 8x8 arrays, one for each piece type and color. You could do it very quickly with bitboards. Perhaps, you could even manage some of the second-order computation, including of additional movements.

Now, by summing the values of a series of squares, you can compute the move cost to traverse those squares with reasonable accuracy. The more higher-order interactions you include, the greater depth with which you can predict move costs.

What is it useful for?
With a fast minimum-path algorithm and these arrays you'd have a common framework for your eval function to consider such questions as:
1) Rabbits within 4 steps of the enemy goal are good.
2) My camel should stay 4 steps away from the enemy elephant.
3) An elephant is blockaded if its move cost in all directions is infinite.
4) A threatened trap is okay as long as a stronger friendly can get there within 4 steps.
5) An elephant is most powerful if it stays within 4 steps of all traps, least powerful if it cannot reach traps within that distance.

Obviously there would be a cost to making this computation. But, given how hard it is in Arimaa to increase search depth by a ply, could this approach create a worthwhile method of improving eval quality at least equivalent to a ply or more of deeper search?

(Another assumption I am making here is that eval and search are both trying to solve the same problem, and that in principle one may trade off one for the other. You may disagree with that premise. But I'll point out that determining whether your elephant can reach a threatened trap given intervening pieces can be looked at from either an eval perspective with a tool like this "distance" tool, or by simply searching farther to find out whether or not the capture is forced -- they start to look like equivalent problems.)

EDIT: clarity / minor corrections

Title: Re: A new way to think about the Arimaa board?
Post by clauchau on Jan 17^th, 2007, 11:58am

It feels like pieces are omnipresent.

For example a centered elephant is seen as protecting the four traps. But that's only true as isolated potentialities - the elephant wouldn't be able to go and protect four friends endangered on the four traps at the same time.

Now, your suggestion is a start anyway. I bet there is some wonderful theory to develop too about sequentiality and parallelism - in thoughts or in actions.

Note aside, this reminds me of a Quantum Chess variant where enemy pieces could be anywhere until they had a chance to be sighted. I don't remember which player - if any - then decided where the pieces happened to be.

Title: Re: A new way to think about the Arimaa board?
Post by fotland on Jan 22^nd, 2007, 6:01pm

Bomb uses this concept of "true distance" in several places. It calculates the true distance from a rabbit to the last row to guide the goal search. It uses true distance from pieces to traps to evaluate trap threats (based on how long it takes a stronger peices to come defend the trap). It uses true distance to evaluate the distance from the center for elephant and camel.

It's expensive to calculate, since you have to look at going around pieces, pulling or pushing them out of the way, and going around or defending traps, but it's worth it.

Title: Re: A new way to think about the Arimaa board?
Post by IdahoEv on Jan 22^nd, 2007, 10:56pm

on 01/22/07 at 18:01:42, fotland wrote:

It's expensive to calculate, since you have to look at going around pieces, pulling or pushing them out of the way, and going around or defending traps, but it's worth it.

In some sense, it's infinitely expensive to calculate depending on how deep you are computing the dependency tree in terms of getting things out of the way, etc. How many levels of dependency deep does Bomb use when making this calculation?

This statement also confirms for me something I've suspected: if you're making good use of the additional information, spending extra time computing your eval is worth it in Arimaa. An order of magnitude increase in the time to compute an eval decreases search depth by less than a single step. Three orders of magnitude increase in eval complexity costs less than a ply in the midgame.

Zombie's eval is still largely inherited from Fairy and is fairly simple and quite fast. I expect this to change quite a bit in 2007.

Title: Re: A new way to think about the Arimaa board?
Post by clauchau on Jan 23^rd, 2007, 3:57am

on 01/15/07 at 19:32:16, IdahoEv wrote:

Given a certain piece type (say, gold dogs), make an 8x8 array representing the approximate move cost associated with each square.

My short-lived bot Quantum Leapfrog was doing that, starting with the elephants and going through weaker and weaker pieces, always fueling the computation with the distances for the pieces already computed, the whole iterated twice (three times wasn't worth the cost). It was using fractional distances to be more accurate.

My conclusion is the whole thing either needs

highly parallel processing if it's going to stay that general - you wish you owned a micro-chip factory - plus some theoretical improvement about the unfortunate ubiquity of helping pieces such an approach tends to allow.
or be highly specialized to a few interesting pieces and squares so that specific knowledge, problem-solving heuristics, tight programming technics, and careful specialized use of the information can be used - Fotland's way with Bomb.

Title: Re: A new way to think about the Arimaa board?
Post by fotland on Feb 2^nd, 2007, 1:13am

on 01/22/07 at 22:56:26, IdahoEv wrote:

Bomb isn't that sophisticated. It calculates a lower bound on the distance, so when the position is complex, the bound won't be as accurate. For rabbits and goals, it's only perfect to 3 steps, but it is usually correct at 4-5 steps, and the bound is reasonable up to about 10 steps. So I can only stop the search 3 steps early, but using a bound early helps a lot with evaluation and move ordering.

Title: Re: A new way to think about the Arimaa board?
Post by Fritzlein on Feb 2^nd, 2007, 8:50am

on 02/02/07 at 01:13:04, fotland wrote:

If the distance-to-goal at four steps isn't perfect, then it can only be used in eval, and not in quiescence search, correct?

Title: Re: A new way to think about the Arimaa board?
Post by fotland on Feb 8^th, 2007, 8:23pm

If the distance to goal is 3 or less and the player to moves still has enough steps left I can stop the search early. This lets me find goals with 3 ply less search.

Otherwise, the distance to goal is part of the evaluation, and I also use it to decide which lines to extend. It also helps with move generation. If distance to goal is small, the goal search sorts moves by the taxicab distance to the pawn nearest to goal.

Title: Re: A new way to think about the Arimaa board?
Post by Fritzlein on Feb 8^th, 2007, 9:55pm

Very interesting. It seems the genius of your capture-based quiescence search is that you only generate capture moves, so you don't waste the time of generating and discarding thousands of other moves. But if you extend the search when you are threatening goal, don't you have to generate all possible defensive moves? Or is there a way to selectively generate only reasonable defensive moves?

To put it another way, there intuitively seems to be a big difference in efficiency between (A) generating exactly the subset of moves you want to extend anyway, and (B) generating all moves from a position and thereafter choosing a small subset to extend. I was extremely impressed to learn that you could do (A) for captures in quiescence search, but I assumed you still had to do (B) for goal threats. If you can do (A) for goal threats as well, I tip my hat to you once again.

But even if you can't generate only valid defensive moves, that's a very clever point about ordering moves by distance to the threating rabbit, for better pruning. Let's call it a B+. And it's another use of distance, both goal distance and taxicab distance. One wonders how many other efficiency-boosting tricks you casually integrated into your code, based on ideas the rest of us wouldn't hit upon in years.