Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 3:38am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Asymmetrical static evaluation? »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Asymmetrical static evaluation?
« Previous topic | Next topic »
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Asymmetrical static evaluation?  (Read 4958 times)
IdahoEv
Forum Guru
*****



Arimaa player #1753

   


Gender: male
Posts: 405
Asymmetrical static evaluation?
« on: Nov 28th, 2006, 5:33pm »
Quote Quote Modify Modify

Question for those who know more about game AI programming than myself.
 
Are static evaluators always symmetrical with respect to which player's turn it is?   That is, for a given board position, will they return the same evaluation score if it is white's turn as opposed to if it is black's turn?
 
It occurs to me that many, maybe even most, positions are of different relative merit depending on side-to-move.   Consider the position of Rc4 Ec3 ed3.    This is an immediately horrible position for gold if it is silver's turn; gold will lose its elephant and the game in three steps.  But if it is gold's turn to move, it's not so bad.
 
You could find out this fact by searching another ply, of course, but if your evaluator takes side-to-move into account you can save yourself that ply of search depth.    
 
Just curious if and how other programmers take that into account.
« Last Edit: Nov 28th, 2006, 5:39pm by IdahoEv » IP Logged
nbarriga
Forum Guru
*****



Almost retired Bot Developer

   


Gender: male
Posts: 119
Re: Asymmetrical static evaluation?
« Reply #1 on: Nov 28th, 2006, 7:28pm »
Quote Quote Modify Modify

I don't think I fully understand the question, but as far as i know, even the sample_c bot takes that into consideration.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Asymmetrical static evaluation?
« Reply #2 on: Nov 28th, 2006, 10:40pm »
Quote Quote Modify Modify

I have read about chess programs that suffer from an even-ply/odd-ply problem.  They always think they are doing better after searching to an odd depth, because they have made an extra move, than they think they are doing after searching to an even depth.  This implies that their static evaluation doesn't take side to move into account.  I don't know what, if anything, chess programmers have done to counteract this.  Maybe if they have quiescence search, and are searching deep enough, it just doesn't matter.
IP Logged

ddyer
Forum Guru
*****






   
WWW

Gender: male
Posts: 66
Re: Asymmetrical static evaluation?
« Reply #3 on: Jan 9th, 2007, 12:00pm »
Quote Quote Modify Modify

The short answer is yes, evaluators are symmetric for current-player and next-player.  I'm not aware of any result that says it has to be that way, but anything else tends to lead to perverse choices.
 
Suppose you wanted to score "piece en prise" as a minus unless it is your move.  Your evaluator would think that you can improve your position by making any move, even those that do not change the actual situation.
 
Because of this effect, searches generally require that everything be evaluated to the same search depth, so that merely kicking the can down the road doesn't affect the result.  But, if everything is evaluated to the same depth, and that depth does not include the "piece en prise" penalty, then effectively the penalty doesn't exist at all.
IP Logged

visit my game site: http://www.boardspace.net/
free online abstract strategy games
IdahoEv
Forum Guru
*****



Arimaa player #1753

   


Gender: male
Posts: 405
Re: Asymmetrical static evaluation?
« Reply #4 on: Jan 19th, 2007, 2:15pm »
Quote Quote Modify Modify

You had me, and then you lost me again.
 
Clearly, if your eval was asymmetric and had a penalty for piece en prise, you would need to search all branches to the same depth.  
 
But it would seem that searching to the same depth would be important anyway, because in most cases a player will be able to improve his position (as far as eval is concerned) by moving.
 
So if you're searching to a consistent depth anyway, why wouldn't checking piece en prise with knowledge of side-to-move be a good idea?
IP Logged
ddyer
Forum Guru
*****






   
WWW

Gender: male
Posts: 66
Re: Asymmetrical static evaluation?
« Reply #5 on: Jan 19th, 2007, 3:51pm »
Quote Quote Modify Modify

suppose you were set up for a queen exchange, but had
the piece-en-prise penalty for only one side.   That would
seriously skew your evaluation of the situation.
IP Logged

visit my game site: http://www.boardspace.net/
free online abstract strategy games
NIC1138
Forum Guru
*****




Arimaa player #65536

   
WWW

Gender: male
Posts: 149
Re: Asymmetrical static evaluation?
« Reply #6 on: Mar 2nd, 2007, 10:48pm »
Quote Quote Modify Modify

I don't know if I really got the question, but I know that go is an asymmetrical game... As most of you may know, white (I think) tends to win by a little margin... Wouldn't be this the only situation where the parity of the ply requires perhaps a different attitude?
 
What about arimaa, do our estimated masters detect any advantage in being the first of the second to play? What's the statistics in the "pro" games? Do we even have enough games to make a statistically-relevant measurement? Smiley
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Asymmetrical static evaluation?
« Reply #7 on: Mar 3rd, 2007, 9:12am »
Quote Quote Modify Modify

Yes, I think you are asking a slightly different question than IdahoEv was, but we have looked at that one a little bit too.
 
If you look only at human vs. bot games, then Gold has a tiny advantage in winning percentage, but not enough to be statistically significant.
 
If you look only at bot vs. bot games, the advantage of Gold is greater, but still not statistically significant.
 
If you look only at human vs. human games, there is a statistically significant advantage for Silver, a much larger gap than the measured advantage for the other two cases.  I can't explain it, but that's what the numbers say.
 
My own opinion is that objectively Gold has a tiny advantage, but it is too small to worry about.  However, the statistics make me keep an open mind that the second setup is worth more than the first move.
IP Logged

JacquesB
Forum Senior Member
****



Arimaa player #2380

   


Gender: male
Posts: 26
Re: Asymmetrical static evaluation?
« Reply #8 on: Mar 4th, 2007, 2:17pm »
Quote Quote Modify Modify

Just two digressions and some questions:
 
Reason A. I would say gold gets the advantage of initiative. If there were some key points to be taken, gold could take them before, but that doesn't sound very likely. In fact, against correct defense, I am still not sure what atacking strategies work, if any.
 
Reason B. But, if Arimaa was solved (Its impossible, I know) I can see a reason why silver could have an advantage: The first move. Gold deploys its pieces blindly while silver answers gold's deployment. Since the game is not solved, it is pointless to make both players deploy their pieces in eight turns each, but that would be smaller advantage for silver. A deployment of silvers's pieces with the current ruleset optimized to beat gold could be the reason why silver could win a perfect game.
 
For me, reason A sounds very small and B even smaller. But I would like stronger players answer: Is there a something to be won in the first moves that justifies a race in which gold could have an advantage? When playing silver, do you deploy your pieces to suit your favorite strategic ideas or are you answering gold's position? (Except for the "two elephants in the same column" issue. BTW Is that really important? I recently played that as gold as was not able to win anything from silver's supposed weakness.)
IP Logged
chessandgo
Forum Guru
*****



Arimaa player #1889

   


Gender: male
Posts: 1244
Re: Asymmetrical static evaluation?
« Reply #9 on: Mar 4th, 2007, 3:02pm »
Quote Quote Modify Modify

Jacques :
 
I'm not aware of any way for silver to take advantage of your B-reason when gold choses one of the most usual setups (99of9-like setups), so I'd say only advantage A is relevant (and indeed it is, whatvever the right strategy might be, rabbit-pulling or activated pieces and attacking, or ..., better have an extra move to do it than being a move down Smiley). So I think gold has an advantage, but we don't play well enough for it to be relevant for a game result ... even for 10000 games results Smiley
 
As for the elpehants on the same column, that's not a big problem, but it makes silver lose a few more steps, roughly.  
 
Please be confident in attacking strategies Smiley and enjoy your games Wink
IP Logged

NIC1138
Forum Guru
*****




Arimaa player #65536

   
WWW

Gender: male
Posts: 149
Re: Asymmetrical static evaluation?
« Reply #10 on: Mar 6th, 2007, 10:28pm »
Quote Quote Modify Modify

Watch out, people, let's not start looking for rasons for the assymetry before we actually detect it! Smiley
 
I'm not very sure about how to estimate the error of the measurement, but from this arcticle
 
http://en.wikipedia.org/wiki/Checking_if_a_coin_is_fair
 
it looks like 10000 games would be enough to detect a 1% unbalance with a 95.45% level of confidence!... It seems 1600 games would be enough to give us an estimative with  2,5% error.
 
From the file  
 
http://arimaa.com/arimaa/download/gameData/ratedgames.tgz
 
It seems there are only  2353 human-human rated  games, of which only 1658 went to "the last consequences". 928 were won by black,  730 by white. Not a very short margin if you ask me!!...
 
The current imbalance would be a 56% chance of black winning, against a 44% of white... Looks like it's detected!
 
In a 4 sigma confidence margin, this would mean an error of E = 4/(2*sqrt( 1658 )) = 4,91%. So the probability of white winning would be inside the interval 39,117%  48,941%
 
Can anyone with more statistical training and feeling less sleepy do that rigorous calcultions to us? Grin  (peer-review is paramount)
 
 
Now, another theory on the causes for the imbalance... Not a systematic one!... It could be that most of the times the game starts with a stronger player inviting a weaker player, and giving him the gold position!  Roll Eyes
 
 
EDIT
Only now I saw that this topic (the way I put it!) is being discussed somewhere else!! Smiley  http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;nu m=1133407311;start=15
 
« Last Edit: Mar 6th, 2007, 10:48pm by NIC1138 » IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Asymmetrical static evaluation?
« Reply #11 on: Mar 7th, 2007, 9:54am »
Quote Quote Modify Modify

You might also find this thread interesting:
http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;nu m=1163650023;start=0#0
IP Logged

JacquesB
Forum Senior Member
****



Arimaa player #2380

   


Gender: male
Posts: 26
Re: Asymmetrical static evaluation?
« Reply #12 on: Mar 7th, 2007, 1:28pm »
Quote Quote Modify Modify

Hi Nicolau
 
From the proportions in your post 928 out of 1658 you must select ridiculously high confidence levels (0.999999) to include 1/2 in the confidence interval.
 
You can use the calculator at:
 
http://www.causascientia.org/math_stat/ProportionCI.html
 
The real value of p (the unknown probability of gold to win) lies:
 
between:   and       with confidence
0.499694   0.618489   0.999999
0.528145   0.590862   0.99
0.535700   0.583441   0.95
 
It is biased at 99% of confidence, but not at 99.9999%
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Asymmetrical static evaluation?
« Reply #13 on: Mar 7th, 2007, 4:56pm »
Quote Quote Modify Modify

on Mar 6th, 2007, 10:28pm, NIC1138 wrote:
It seems there are only  2353 human-human rated  games, of which only 1658 went to "the last consequences". 928 were won by black,  730 by white. Not a very short margin if you ask me!!...
[...]
Now, another theory on the causes for the imbalance... Not a systematic one!... It could be that most of the times the game starts with a stronger player inviting a weaker player, and giving him the gold position!

Yes, the raw numbers are not to be trusted, because often the stronger player will invite, giving himself the Silver pieces.  In 2478 rated HvH games in my database, the Silver player was rated an average of 34.7 rating points higher than the Gold player.  It is beside the point to consider the confidence interval of a statistic that is known to be biased in the first place.
 
In the other threads where this question was discussed, I accounted for possible color imbalance due to invitations by only counting pairs of games where the two players involved played with reversed colors.  JacquesB, I would  be interested to hear your comments on the confidence of the statistics I gave here: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;nu m=1163650023;start=0#0
« Last Edit: Mar 7th, 2007, 5:25pm by Fritzlein » IP Logged

IdahoEv
Forum Guru
*****



Arimaa player #1753

   


Gender: male
Posts: 405
Re: Asymmetrical static evaluation?
« Reply #14 on: Mar 7th, 2007, 6:16pm »
Quote Quote Modify Modify

on Mar 7th, 2007, 4:56pm, Fritzlein wrote:
often the stronger player will invite, giving himself the Silver pieces.

 
Which reminds me ... A possible gameroom feature I could work up on the dev server: an invite option with side set to "random".   Neither player knows which side he will play until after the invite is accepted.    I know I would use it for almost all of my invites; I hate the stress of deciding which side to offer.
« Last Edit: Mar 7th, 2007, 6:16pm by IdahoEv » IP Logged
Pages: 1 2 3  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.