Author |
Topic: Asymmetrical static evaluation? (Read 5144 times) |
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender: 
Posts: 405
|
 |
Asymmetrical static evaluation?
« on: Nov 28th, 2006, 5:33pm » |
 Quote  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:
Posts: 119
|
|
Re: Asymmetrical static evaluation?
« Reply #1 on: Nov 28th, 2006, 7:28pm » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Asymmetrical static evaluation?
« Reply #2 on: Nov 28th, 2006, 10:40pm » |
Quote 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
Gender:
Posts: 66
|
|
Re: Asymmetrical static evaluation?
« Reply #3 on: Jan 9th, 2007, 12:00pm » |
Quote 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:
Posts: 405
|
|
Re: Asymmetrical static evaluation?
« Reply #4 on: Jan 19th, 2007, 2:15pm » |
Quote 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
Gender:
Posts: 66
|
|
Re: Asymmetrical static evaluation?
« Reply #5 on: Jan 19th, 2007, 3:51pm » |
Quote 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
Gender:
Posts: 149
|
|
Re: Asymmetrical static evaluation?
« Reply #6 on: Mar 2nd, 2007, 10:48pm » |
Quote 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? 
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Asymmetrical static evaluation?
« Reply #7 on: Mar 3rd, 2007, 9:12am » |
Quote 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:
Posts: 26
|
|
Re: Asymmetrical static evaluation?
« Reply #8 on: Mar 4th, 2007, 2:17pm » |
Quote 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:
Posts: 1244
|
|
Re: Asymmetrical static evaluation?
« Reply #9 on: Mar 4th, 2007, 3:02pm » |
Quote 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 ). 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
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 and enjoy your games 
|
|
IP Logged |
|
|
|
NIC1138
Forum Guru
Arimaa player #65536
Gender:
Posts: 149
|
|
Re: Asymmetrical static evaluation?
« Reply #10 on: Mar 6th, 2007, 10:28pm » |
Quote Modify
|
Watch out, people, let's not start looking for rasons for the assymetry before we actually detect it!
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?  (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! 
EDIT
Only now I saw that this topic (the way I put it!) is being discussed somewhere else!! 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 |
|
|
|
JacquesB
Forum Senior Member
Arimaa player #2380
Gender:
Posts: 26
|
|
Re: Asymmetrical static evaluation?
« Reply #12 on: Mar 7th, 2007, 1:28pm » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Asymmetrical static evaluation?
« Reply #13 on: Mar 7th, 2007, 4:56pm » |
Quote 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:
Posts: 405
|
|
Re: Asymmetrical static evaluation?
« Reply #14 on: Mar 7th, 2007, 6:16pm » |
Quote 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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print