Welcome, Guest. Please Login or Register.
Aug 23rd, 2019, 2:58pm

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum Arimaa evaluation functions


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Arimaa evaluation functions
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Arimaa evaluation functions  (Read 1489 times)
fotland
Forum Guru
*****



Arimaa player #211

   


Gender: male
Posts: 216
Arimaa evaluation functions
« on: Oct 6th, 2003, 3:02pm »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1412
Re: Arimaa evaluation functions
« Reply #1 on: Oct 6th, 2003, 6:07pm »
Quote Quote Modify 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: male
Posts: 216
Re: Arimaa evaluation functions
« Reply #2 on: Oct 6th, 2003, 11:28pm »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1412
Re: Arimaa evaluation functions
« Reply #3 on: Oct 7th, 2003, 3:34am »
Quote Quote Modify 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: male
Posts: 216
Re: Arimaa evaluation functions
« Reply #4 on: Oct 7th, 2003, 11:00pm »
Quote Quote Modify 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

   
WWW

Gender: male
Posts: 145
Re: Arimaa evaluation functions
« Reply #5 on: Nov 11th, 2003, 2:25pm »
Quote Quote Modify 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 Smiley 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)

  toby_hudson  


Gender: male
Posts: 1412
Re: Arimaa evaluation functions
« Reply #6 on: Nov 11th, 2003, 7:07pm »
Quote Quote Modify 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

   
WWW

Gender: male
Posts: 145
Re: Arimaa evaluation functions
« Reply #7 on: Nov 13th, 2003, 7:50am »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1412
Re: Arimaa evaluation functions
« Reply #8 on: Nov 13th, 2003, 11:28am »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1412
Re: Arimaa evaluation functions
« Reply #9 on: Nov 19th, 2003, 6:26am »
Quote Quote Modify 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: male
Posts: 216
Re: Arimaa evaluation functions
« Reply #10 on: Nov 20th, 2003, 12:52am »
Quote Quote Modify Modify

Speedy tracks the total material incrementally, when making a move.  Otherwise everything is recalculated from scratch.
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.