Welcome, Guest. Please Login or Register.
Dec 14th, 2024, 7:30am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « (no) absolute score values for pieces? »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   (no) absolute score values for pieces?
« Previous topic | Next topic »
Pages: 1 2 3 4  ...  9 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: (no) absolute score values for pieces?  (Read 40262 times)
gern
Forum Newbie
*



Arimaa player #215

   


Gender: male
Posts: 1
Re: (no) absolute score values for pieces?
« Reply #15 on: Sep 7th, 2003, 10:31am »
Quote Quote Modify Modify

In Bot Occam, the values of the pieces vary depending what is on the
board.   When a piece type goes away for instance,   I revalue every
piece on the board as if that piece never was a part of the game.
 
For example,  if the dogs go away, there should not be a huge gap
between the value of the cats and the horses.   It's as if the horses
now become DOGS.     In arimaa the values
of the piece are relative to each other,  not like in chess where the
value is based more on the power of their moves.
 
Don
IP Logged
clauchau
Forum Guru
*****



bot Quantum Leapfrog's father

   
WWW

Gender: male
Posts: 145
Re: (no) absolute score values for pieces?
« Reply #16 on: Oct 3rd, 2003, 5:50pm »
Quote Quote Modify Modify

By the way Camels are overrated  Smiley
 
In the games I traded it, I hardly felt the trade like a loss. The truth is, if you rate it high, you have to defend it and use part of your elephant, or at least keep it far from your opponent's elephant, reducing the value you intially saw in it.
 
Funny paradox, isn't it - if they are worth a lot then they aren't worth that lot  Wink
 
Hence I feel better putting values elsewhere in the first place.
 
Claude
IP Logged
fotland
Forum Guru
*****



Arimaa player #211

   


Gender: male
Posts: 216
Re: (no) absolute score values for pieces?
« Reply #17 on: Oct 5th, 2003, 1:16am »
Quote Quote Modify Modify

Would you trade a camel for two horses, or a horse and a dog?
 
The way I think of it is that if I trade camel for camel, then the horses become camels, so now I have two instead of one Smiley
 
David
IP Logged
haizhi
Forum Senior Member
****



Arimaa player #350

   


Gender: male
Posts: 45
Re: (no) absolute score values for pieces?
« Reply #18 on: Nov 22nd, 2003, 3:19pm »
Quote Quote Modify Modify

I have some thoughts about that. Maybe we can use TD learning to set piece values for every situation since it's enumable, say, one side lost 1 camel and  the other lost 1 horse, just run a game initially set up this way for 1000 times.
IP Logged
haizhi
Forum Senior Member
****



Arimaa player #350

   


Gender: male
Posts: 45
Re: (no) absolute score values for pieces?
« Reply #19 on: Nov 22nd, 2003, 3:37pm »
Quote Quote Modify Modify

But it only works when you doesn't plan putting new feature in your eval, otherwise too many recalculating.
IP Logged
fotland
Forum Guru
*****



Arimaa player #211

   


Gender: male
Posts: 216
Re: (no) absolute score values for pieces?
« Reply #20 on: Nov 22nd, 2003, 11:10pm »
Quote Quote Modify Modify

I thought about trying to learn weights for pieces, but I found that positional values are much higher in arimaa than in chess programs, so the exact values of the pieces are not very important.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: (no) absolute score values for pieces?
« Reply #21 on: Oct 7th, 2005, 10:59pm »
Quote Quote Modify Modify

After reading Haizhi's thesis about his bot, I was impressed with how much I don't know about game programming, and how useless my strategic understanding of Arimaa would be in helping to create a stronger bot.  I can sometimes specifically describe what I think the weaknesses of a given bot are, and the bot-bashing hall of fame is testament to how small flaws in bot evaluation can be parlayed into outrageous losses, but increasing human understanding of bot weakness doesn't necessarily suggest any quick fixes.
 
That said, if there is one tiny area where cheap gains in bot strength seem to be available, it would be in material evaluation.  Material advantage is (and should be) the bedrock of the evaluation function, but static piece values just aren't very good, and Occam's fix, while helpful, doesn't apply in many situations.  Let me add a couple of examples to the many already proposed:
 
(1) I believe that as the first pieces traded, a camel is equal to a horse and a dog, i.e. EHHDDCCRRRRRRRR = EMHDCCRRRRRRRR.  However, every even trade thereafter makes the camel worth relatively less.  If a pair of horses comes off, then the camel is palpably worse than the horse and dog although Occam can't collapse any piece categories and the 99of9 system acknowledges no difference.  EHDDCCRRRRRRRR > EMDCCRRRRRRRR.
 
(2) The value of rabbits increases, not just when rabbits disappear (as the 99of9 system has it) but also when pieces disappear.  How does a camel compare to four rabbits?  It is worth more in the opening, i.e.  EMHHDDCCRRRR > EHHDDCCRRRRRRRR, but less if we trade off HDC, weakening goal defense, i.e. EMHDCRRRR < EHDCRRRRRRRR.  Notice that neither Occam nor the 99of9 system can have a different inequality in the former case than in the latter case.
 
In general, I agree with Clauchau that camels are overvalued, at least by bots.  This is because bots are hand-tuned to value camels approximately correctly in the opening, but stick with this high value even as they get less and less valuable later in the game.
 
 
I'll post more ramblings in a bit.
« Last Edit: Oct 8th, 2005, 12:17am by Fritzlein » IP Logged

PMertens
Forum Guru
*****



Arimaa player #692

   
WWW

Gender: male
Posts: 437
Re: (no) absolute score values for pieces?
« Reply #22 on: Oct 8th, 2005, 12:54am »
Quote Quote Modify Modify

You need to be very carefull how to tune this, because humans will learn very fast how to trigger suicidal moves.
 
That beeing said I honestly doubt that a more complex weighting of just the piece-values is worth the effort - just because the effort is so enormous.
 
The value is not only dependent on the available pieces, but also on the position on the board.
 
What is the value of a blocked phant  Wink
(see bait and tackle)
 
What is the value of a camel hiding at home ?
 
Like I said in the beginning: I doubt it will bring to much advantage ...
but then I should try to come up with a better idea, shouldn't I ?  Embarassed
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: (no) absolute score values for pieces?
« Reply #23 on: Oct 8th, 2005, 1:49am »
Quote Quote Modify Modify

Well, certainly positional factors are going to weigh heavily, and be very tricky to evaluate.  Yes, an elephant blockade may be worth more or less than a dog depending on a number of factors.  Yes, a hiding camel is worth less than an active camel.  Etc. Etc.
 
But that doesn't mean we shouldn't try to evaluate material more accurately.  We are starting to pile up endgame examples where material misevaluation, quite apart from positional factors, has been fatal to Bomb.  For example it declined to trade its camel for a dog plus a rabbit of mine when trading would have given Bomb a clearer material advantage than not trading.
 
Of course, a better evaluation function is easier to speculate about than to formulate, so maybe you are right that it requires too much effort.  Here's one try that doesn't quite work, but may be of interest:
 
First line up the pieces (not including rabbits) from strongest to weakest on each side.  Winning the "strongest vs. strongest" is worth 128 points.  Winning "2nd strongest vs. 2nd strongest" is worth 64 points, and so on, with each contest worth half the previous.  After totalling up those points, let the rabbits each be worth 1024 divided by the opponent's goal defense, i.e. 1024/(R + 3P), where R is the number of opposing rabbits and P is the number of opposing pieces.
 
Here's how some opening trades are evaluated by this system:
 
M for HD is +21
M for HH is -11
M for HCR is -17
M for RRRR is -66
H for DC is -19
E for RRRRR is +16
E for RRRRRR is -31
 
Clearly I am over-valuing the rabbits and undervaluing horses.  Maybe the behavior I want not only can't be captured by a simple formula, it can't be captured by a moderately complex formula.  Sad
IP Logged

jdb
Forum Guru
*****



Arimaa player #214

   


Gender: male
Posts: 682
Re: (no) absolute score values for pieces?
« Reply #24 on: Oct 8th, 2005, 8:44am »
Quote Quote Modify Modify

In my opinion, this is a very important topic for anyone wanting to create a quality evaluation function.
 
As Pmertens pointed out, if the eval places a large value on positional factors, humans will figure out how to exploit that and suicidal moves will result.
 
The 2005 version of clueless uses absolute piece values, but the rabbits follow something like the 99of9 system. This approach is not really good enough.
 
In order to manage the complexity, I was considering using two sets of piece values. One for the opening and one for the endgame. As Fritzlein mentioned, the piece values do depend on the game situation.  
 
It is likely safer to select criteria that cant be undone. For example, changing material values if a horse/camel is hostage, would be risky. Using something like the enemy camel is captured would be better, since it can't be undone. Anything that can be undone could be exploited by a human quite easily.
 
Clueless uses these values:
 
Cat      1600
Dog     1800
Horse  3500
Camel  5500
Elephant 22000
 
  // CUMULATIVE RABBIT VALUE
  // 1st rabbit is 3000
  // 2nd is 2000
  // 3rd-5th is 1500
  // 6-8th is 1200   Changed to 1400
  // 9th and up also 1200 for test position only, Changed to error condition
  public static final int rabbit_value[] = {
    0, 3000, 5000, 6500, 8000, 9500, 10900, 12300, 13700, 14900, 16100, -1,
    -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1
  };
IP Logged
PMertens
Forum Guru
*****



Arimaa player #692

   
WWW

Gender: male
Posts: 437
Re: (no) absolute score values for pieces?
« Reply #25 on: Oct 8th, 2005, 11:07am »
Quote Quote Modify Modify

one little idea, that might be slightly off Topic:
 
Bots usually do not mind exchanging pieces.
Does any bot check wether he leads on material or not ?
 
If I am behind a dog, then It is usually not smart to trade horses.
 
That also means, that the values on both sides must be different. (I am not sure if anyone implemented that)
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: (no) absolute score values for pieces?
« Reply #26 on: Oct 8th, 2005, 1:49pm »
Quote Quote Modify Modify

on Oct 8th, 2005, 11:07am, PMertens wrote:
one little idea, that might be slightly off Topic:
 
Bots usually do not mind exchanging pieces.
Does any bot check wether he leads on material or not ?

 
That's not off-topic at all, and in fact is an essential feature of what I am trying to do with my evaluation function.  Generally if you are behind on material, trading off pieces will make it worse, but also there are material deficits that get better through trading.  For example two rabbits is worth less than a dog at first, but trading off cats and rabbits makes the disadvantage less, and may turn it into an advantage.
 
I've re-tweaked my proposal, and now it is starting to give semi-reasonable results, although there are still some problems.  I still give great weight to numerical superiority, but now there's a slightly better balance between pieces and rabbits.  (By piece I mean any non-rabbit piece.)   My new plan is:
 
(1) Line up the pieces from strongest to weakest on both sides.  If one side has fewer pieces, they must contributed rabbits until all the opposing pieces are matched.
 
(2) Winning the top matchup is worth 128, and each successive matchup is worth 2/3 of the previous.
 
(3) The leftover rabbits each score 768/(R+3P) where R and P are respectively the number of rabbits and pieces the opponent has left.
 
Here are some initial trade values:
 
R free = +30
C free = +51
D free = +68
H free = +116
M free = +201
E free = +329
 
C for R = +19
C for RR = -13
D for RR = +4
D for CR = -17
MD for MCR = -14
MHD for MHCR = -8
MHHD for MHHCR = +2
H for D = +38
H for DR = +4
H for DC = -24
M for HD = -2
MH for HHD = -30
M for HCR = -13
M for HH = -59
H for RRR = +9
H for RRRR = -24
M for RRRRR = +28
MHDC for HDCRRRRR = +22 Sad
E for MH = -16 Sad
 
and some endgames:
ERR vs. CCRR = -168
ERRR vs. CCRR = -21  
EDRR vs. ECCRR = -94
ERRR vs. ECR = -6
EDRRR vs ECCRR = -2
 
Well, the formula returned reasonable values for a lot of trades, but the last two trades are wrong, I believe.   The endgame values are a bit dodgy, but not wholly unreasonable given that positional goal threat factors will often overwhelm them.  I have a slight preference for the former side in either of the last two endgames, but my system has them even.  Ah, well, back to the drawing board.
« Last Edit: Oct 8th, 2005, 1:54pm by Fritzlein » IP Logged

99of9
Forum Guru
*****




Gnobby's creator (player #314)

  toby_hudson  


Gender: male
Posts: 1413
Re: (no) absolute score values for pieces?
« Reply #27 on: Oct 9th, 2005, 6:58pm »
Quote Quote Modify Modify

I'm really glad to see this topic refreshed.  I'll have more to contribute later, but for now, I think I can identify one of Fritz's main problems:
on Oct 8th, 2005, 1:49pm, Fritzlein wrote:
(2) Winning the top matchup is worth 128, and each successive matchup is worth 2/3 of the previous.

I think this outrageously undervalues the topmost matchup.  Losing global domination is devastating, it is worth much more than a 50% bonus on secondary domination.
 
I think this is why you're unhappy with the elephant sacrifice results.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: (no) absolute score values for pieces?
« Reply #28 on: Oct 9th, 2005, 10:56pm »
Quote Quote Modify Modify

on Oct 9th, 2005, 6:58pm, 99of9 wrote:
I think I can identify one of Fritz's main problems:
I think this outrageously undervalues the topmost matchup.

 
You hit the nail on the head.  I'm going to try to run the numbers again with the values of the matchups being something more like
 
1st: 256
2nd: 256/3
3rd: 256/5
4th: 256/7
etc.
 
This will also help correct some of the dubious endgame values.  I'll have to run all the numbers again to be sure, but I think that with this improvement, I might prefer this dynamic system to antyhing that has been published about bots Haizhi, Clueless, Bomb, Occam, and Gnobot.  Nevertheless, I'll hold off naming it until I think it will work.  Smiley
IP Logged

99of9
Forum Guru
*****




Gnobby's creator (player #314)

  toby_hudson  


Gender: male
Posts: 1413
Re: (no) absolute score values for pieces?
« Reply #29 on: Oct 9th, 2005, 11:45pm »
Quote Quote Modify Modify

on Oct 9th, 2005, 10:56pm, Fritzlein wrote:
I might prefer this dynamic system to antyhing that has been published about bots Haizhi, Clueless, Bomb, Occam, and Gnobot.

I think you could well be right, it's certainly the best thinking I've seen published about this.
 
And thanks for your tipoff that Haizhi's thesis was online... I'm just reading it now.  Congratulations on submitting Haizhi!
« Last Edit: Oct 9th, 2005, 11:45pm by 99of9 » IP Logged
Pages: 1 2 3 4  ...  9 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.