Author |
Topic: Arimaa evaluation functions (Read 1987 times) |
|
fotland
Forum Guru
Arimaa player #211
Gender: 
Posts: 216
|
 |
Arimaa evaluation functions
« on: Oct 6th, 2003, 3:02pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Arimaa evaluation functions
« Reply #1 on: Oct 6th, 2003, 6:07pm » |
Quote Modify
|
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.
|
| « Last Edit: Oct 6th, 2003, 6:12pm by 99of9 » |
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Arimaa evaluation functions
« Reply #2 on: Oct 6th, 2003, 11:28pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa evaluation functions
« Reply #3 on: Oct 7th, 2003, 3:34am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Arimaa evaluation functions
« Reply #4 on: Oct 7th, 2003, 11:00pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Arimaa evaluation functions
« Reply #5 on: Nov 11th, 2003, 2:25pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa evaluation functions
« Reply #6 on: Nov 11th, 2003, 7:07pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Arimaa evaluation functions
« Reply #7 on: Nov 13th, 2003, 7:50am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa evaluation functions
« Reply #8 on: Nov 13th, 2003, 11:28am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa evaluation functions
« Reply #9 on: Nov 19th, 2003, 6:26am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Arimaa evaluation functions
« Reply #10 on: Nov 20th, 2003, 12:52am » |
Quote Modify
|
Speedy tracks the total material incrementally, when making a move. Otherwise everything is recalculated from scratch.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print