Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Arimaa evaluation functions
        
(Message started by: fotland on Oct 6^th, 2003, 3:02pm)

Title: Arimaa evaluation functions
Post by fotland on Oct 6^th, 2003, 3:02pm

Is anyone interested in comparing notes on evaluation functions? Speedy's is big, but not very complex.

Evaluation terms include:

Material balance.

Piece/square tables for Elephant, camel/horse, dog/cat, and rabbit.

Advanced rabbits: goal distance and local balance of strength.

Traps: for each piece and trap, the likelihood of being trapped.

Mobility: pieces frozen, pieces surrounded, access to the center for elephant and camel, and pieces tied down defending traps.

Is anyone using anything else?

-David

Title: Re: Arimaa evaluation functions
Post by 99of9 on Oct 6^th, 2003, 6:07pm

Firsttry has this so far:

* material balance (99 system oy oy oy)
* rabbit advancement, just how far forward so far
* "control" of traps
* frozenness

so only one of them you might be able to add ... trap control, ie number of pieces/strength of pieces around each trap.

Title: Re: Arimaa evaluation functions
Post by fotland on Oct 6^th, 2003, 11:28pm

I used to have trap control, but I took it out. For example, say you have a elephant and camel at a trap and the opponent has only an elephant. This is good for the opponent, since he can pin your camel near the trap and force your elephant to defend it. Now he is up a camel on the rest of the board. Naveed used this strategy to beat speedy many times, until I took out this trap control term.

Title: Re: Arimaa evaluation functions
Post by 99of9 on Oct 7^th, 2003, 3:34am

I think that just means you got the definition of control slightly off. Elephants are strong beasts... if one player has an elephant at a trap, the other player cannot be considered to control the trap.

Title: Re: Arimaa evaluation functions
Post by fotland on Oct 7^th, 2003, 11:00pm

I actually have this concept. An elephant or two pieces controls a trap, and trap control is a small positive evaluation (about 0.1 of the first rabbit). Any more than that and it makes its elephant hang out at an enemy trap rather than pulling enemy pieces around.

Title: Re: Arimaa evaluation functions
Post by clauchau on Nov 11^th, 2003, 2:25pm

Quantum Leapfrog's evaluation is about the total density fields of rabbits on the goal rows.

The presence of every single animal is expanded over the whole board with an exponential decrease ratio as we go farther from its actual position. It is weakened along by the other density fields.

Several passes over the whole fauna increases the accuracy as those fuzzy obstacles get mutually more accurate.

I've been thinking of this for a year but it's only working fine since Monday. You know... My marriage :) and the time needed to get the code simple and flawless.

Unfortunately

Three passes over the fauna would already take too much time. Two passes allows 700 positions to be evaluated per second on my 2GHz pc.
This is enough to make a full 2-ply alpha-beta search avalaible in less than a minute, often even in less than ten seconds (with the killer heuristic and the moves first ordered by a full 1-ply search), but doesn't allow to reach a decent 4-ply search, which I think is the minimum depth required to get us humans thinking. A 3-ply search might be over optimistic.
The resulting play doesn't have the magical touch I dreamt of. It certainly is no challenge to Speedy and Gnobot.
It plays much like Occam. So far so much for originality.

Claude

Title: Re: Arimaa evaluation functions
Post by 99of9 on Nov 11^th, 2003, 7:07pm

Clauchau

It sounds like your evaluation function is just too heavy. Expanding up to 32 pieces over 64 positions and doing an exponential function (much harder than an add or subtract) sounds like 32*64*many_float_operations*num_passes, which is a lot. Compared to the typical evaluation function feature which would consider each piece, it's position, and normally it's 4 neighbours (to tell if it's frozen), which adds up to: 32*4*only_a_few_float_ops.

In fact I tried an eval function which included comparing the position of all my pieces to the position of all his pieces (16*16*exp), which ended up being too expensive too.

A simple saving you might make is to use a power law instead of an exponential: 1/d^2 would only require two divides, which should be cheaper than exp (??).

But I think in the end, if you're not using heavy selectivity, you have to go for a function which is as fast as is reasonably possible. My selectivity requires something more expensive on the first few ply, but since that's not the bulk of evals, I think I can afford it.

... just ramblings ...

But anyway, since you're the top rated bot-developer, you should be able to implement your skills into a fierce bot one day.

99of9

Title: Re: Arimaa evaluation functions
Post by clauchau on Nov 13^th, 2003, 7:50am

The exponential law used in Leapfrog is 1/4^d where d is the distance. It's no big deal, it only needs a division by 4 as we go a square farther.

I first had planned to use 1/d and might still have a try at it. It would be better than 1/d^2 if we were looking for some analogy with physical theories in a two-dimensional world.

Claude

Title: Re: Arimaa evaluation functions
Post by 99of9 on Nov 13^th, 2003, 11:28am

Actually my comment was silly anyway, this kind of thing should be tabulated - then it doesn't matter how complex the evaluation function is.

If you compute a table right at the start:

Field[pos1][pos2] = function( distance(pos1,pos2) )

Then lookups will be very fast. You could even have one table for every different pair of piece types, so you wouldn't need to multiply by piece strength after a lookup:

Field[piece1][piece2][pos1][pos2]

But regardless, I still think the 32*64 factor is what kills you in the end.

99of9

Title: Re: Arimaa evaluation functions
Post by 99of9 on Nov 19^th, 2003, 6:26am

Just interested - do other bot developers have "incremental" evaluation functions... which keep the evaulation up to date based on the moves made, or do they just fully evaluate the whole board every time an evaluation is required?

The incremental version would be much quicker, but also much harder to code I would think. Gnobby doesn't use this, but I'm wondering if maybe it should.

Title: Re: Arimaa evaluation functions
Post by fotland on Nov 20^th, 2003, 12:52am

Speedy tracks the total material incrementally, when making a move. Otherwise everything is recalculated from scratch.