Author |
Topic: Rating of a perfect chess player (Read 6522 times) |
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender: 
Posts: 882
|
 |
Re: Rating of a perfect chess player
« Reply #15 on: Nov 1st, 2004, 7:35am » |
 Quote  Modify
|
Fritzlein,
You've provided a great example of the difference between what I call a perfect player and a player that maximizes its ELO rating. My version of perfect player would not risk a loss, even if the expected ELO value were higher by taking the risk.
With this description of the ELO maximizer, we now must consider a co-evolving landscape where all ELO maximizers must tune their estimates of each other. And their estimates of their opponents' estimates. This is closer to the human game. Did Omar have this in mind specifically for the Arimaa machine intelligence question?
|
|
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #16 on: Nov 1st, 2004, 3:25pm » |
Quote Modify
|
It's quite interesting that an imperfect player could possibly have a higher ELO than the highest rated perfect player.
But I was really just interested in the rating of a perfect player as modeled by the random perfect player described by Toby.
I ran some experiments recently to see what the rating of a random perfect player would be in tic-tac-toe. With zero being the rating of the random player the rating of a random perfect player comes out to about 540.
Of course as we've discussed before, the rating of a player depends somewhat on the other players in the field.
What I did for the other players was to limit them by the number of plys they search. The players look a certain number of plys ahead using only win or lose information (no heuristics) to narrow down the list of valid moves and randomly select from the remaining moves. So player 0 looks zero ply ahead (it is the random player). Player 1 looks one ply ahead and selects the winning move if there is one; otherwise picks a random move. Player 2 looks two plys ahead and is able to block a simple win and find one move wins. At player 6 we have the perfect player as defined by Toby's definition of random perfect.
I had the players play 2000 games against each other player. Half of the games as the first to move (X) and the other half as second (O). Here is the data from those runs.
p1-p0 would mean player 1 against player 0.
p0-p0
as X wins=577 draws=121 lost=302 games=1000
as O wins=288 draws=137 lost=575 games=1000
p1-p0
as X wins=831 draws=72 lost=97 games=1000
as O wins=515 draws=81 lost=404 games=1000
p1-p1
as X wins=693 draws=40 lost=267 games=1000
as O wins=260 draws=51 lost=689 games=1000
p2-p0
as X wins=896 draws=93 lost=11 games=1000
as O wins=653 draws=258 lost=89 games=1000
p2-p1
as X wins=864 draws=110 lost=26 games=1000
as O wins=649 draws=211 lost=140 games=1000
p2-p2
as X wins=302 draws=515 lost=183 games=1000
as O wins=191 draws=495 lost=314 games=1000
p3-p0
as X wins=935 draws=55 lost=10 games=1000
as O wins=692 draws=215 lost=93 games=1000
p3-p1
as X wins=945 draws=43 lost=12 games=1000
as O wins=674 draws=175 lost=151 games=1000
p3-p2
as X wins=512 draws=350 lost=138 games=1000
as O wins=232 draws=459 lost=309 games=1000
p3-p3
as X wins=541 draws=264 lost=195 games=1000
as O wins=168 draws=296 lost=536 games=1000
p4-p0
as X wins=950 draws=46 lost=4 games=1000
as O wins=750 draws=211 lost=39 games=1000
p4-p1
as X wins=942 draws=46 lost=12 games=1000
as O wins=734 draws=192 lost=74 games=1000
p4-p2
as X wins=531 draws=376 lost=93 games=1000
as O wins=213 draws=614 lost=173 games=1000
p4-p3
as X wins=534 draws=330 lost=136 games=1000
as O wins=170 draws=502 lost=328 games=1000
p4-p4
as X wins=318 draws=518 lost=164 games=1000
as O wins=149 draws=513 lost=338 games=1000
p5-p0
as X wins=950 draws=35 lost=15 games=1000
as O wins=723 draws=159 lost=118 games=1000
p5-p1
as X wins=959 draws=27 lost=14 games=1000
as O wins=616 draws=136 lost=248 games=1000
p5-p2
as X wins=785 draws=190 lost=25 games=1000
as O wins=222 draws=503 lost=275 games=1000
p5-p3
as X wins=762 draws=199 lost=39 games=1000
as O wins=222 draws=470 lost=308 games=1000
p5-p4
as X wins=682 draws=282 lost=36 games=1000
as O wins=207 draws=504 lost=289 games=1000
p5-p5
as X wins=697 draws=254 lost=49 games=1000
as O wins=57 draws=266 lost=677 games=1000
p6-p0
as X wins=960 draws=40 lost=0 games=1000
as O wins=790 draws=210 lost=0 games=1000
p6-p1
as X wins=972 draws=28 lost=0 games=1000
as O wins=768 draws=232 lost=0 games=1000
p6-p2
as X wins=749 draws=251 lost=0 games=1000
as O wins=153 draws=847 lost=0 games=1000
p6-p3
as X wins=762 draws=238 lost=0 games=1000
as O wins=163 draws=837 lost=0 games=1000
p6-p4
as X wins=675 draws=325 lost=0 games=1000
as O wins=96 draws=904 lost=0 games=1000
p6-p5
as X wins=702 draws=298 lost=0 games=1000
as O wins=100 draws=900 lost=0 games=1000
p6-p6
as X wins=0 draws=1000 lost=0 games=1000
as O wins=0 draws=1000 lost=0 games=1000
I used this data to iteratively calculate the ratings using the performance rating formula. The ratings of the players came out as:
p1=94 p2=331 p3=364 p4=399 p5=441 p6=540
with p0 fixed at 0.
Initially it shows the same decreasing returns in ratings with increasing plys as seen in Chess and other games. But when it starts getting close to perfect the ratings shoot up again.
If chess also has a similar curve (especially when it approaches random perfect) then trying to determine the rating of the random perfect player by extropolating will probably not be possible (as Karl had mentioned earlier).
It would be interesting to see if this kind of a curve also appears in games which are slightly more complex than tic-tac-toe.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Rating of a perfect chess player
« Reply #17 on: Nov 1st, 2004, 6:59pm » |
Quote Modify
|
on Nov 1st, 2004, 3:25pm, omar wrote:
p0-p0
as X wins=577 draws=121 lost=302 games=1000
as O wins=288 draws=137 lost=575 games=1000
p1-p1
as X wins=693 draws=40 lost=267 games=1000
as O wins=260 draws=51 lost=689 games=1000
p2-p2
as X wins=302 draws=515 lost=183 games=1000
as O wins=191 draws=495 lost=314 games=1000
p3-p3
as X wins=541 draws=264 lost=195 games=1000
as O wins=168 draws=296 lost=536 games=1000
p4-p4
as X wins=318 draws=518 lost=164 games=1000
as O wins=149 draws=513 lost=338 games=1000
p5-p5
as X wins=697 draws=254 lost=49 games=1000
as O wins=57 draws=266 lost=677 games=1000
p6-p6
as X wins=0 draws=1000 lost=0 games=1000
as O wins=0 draws=1000 lost=0 games=1000
|
|
This is bad news for your project with respect to chess. The perfect player is p6. Plot the drawing percentages of games between equal players of increasing strength from p0 to p5. How the heck would you extrapolate that forward?
It is interesting that this exactly models one of the difficulties you anticipated for chess: different styles of player have different drawing percentages. The even-ply players are good at drawing, whereas the odd-ply players are good at winning. So being a stronger player doesn't necessarily translate into drawing more.
|
| « Last Edit: Nov 1st, 2004, 6:59pm by Fritzlein » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #18 on: Nov 2nd, 2004, 9:27am » |
Quote Modify
|
Yes, it doesn't look very promising. The only hope is that maybe this was too simple of a problem and so has a very descrete and choppy space. Maybe the space for chess is more smoother. Also the behavior of the players I used was very descrete and choppy. The behaviour of real players would be more smooth. So it may still be that the plot for chess is more smoother.
Even so, if the curve shoots up suddenly when it approachs perfect play, then extropolating will cause us to predict a much higher rating for perfect play than what it actually is.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #19 on: Nov 6th, 2004, 12:12pm » |
Quote Modify
|
I finally got around to finding the data and trying out this proposal. The trend in the data is much better for chess than it was for T-T-T. I would say that a perfect chess player is probably around 3700.
Have a look at the graph and see what you think.
http://arimaa.com/arimaa/rating/humanChessDrawPerc.xls
You might have to right click on the link and select 'Save Link Target As' to download it.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Rating of a perfect chess player
« Reply #20 on: Nov 6th, 2004, 1:09pm » |
Quote Modify
|
Interesting.
A linear regression through those points would give a 100% draw at a rating of 4500. But I can see why you estimated smaller, because the points do seem to be curving up a little.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Rating of a perfect chess player
« Reply #21 on: Nov 6th, 2004, 2:15pm » |
Quote Modify
|
Interesting graph. I'm pretty skeptical of the extrapolation to 3700. The points that most make it look tipped up are the first and the last, which are based on 5 and 8 games respectively. Throw out those unreliable points and you've got a very different picture.
It's interesting that the projected perfect rating on this basis is so high.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #22 on: Nov 7th, 2004, 10:50pm » |
Quote Modify
|
The 3700 number is really just a bit of an educated guess. A straight line would suggest a higher rating, especially if we throw out the first and last points. However, I have a feeling that it isn't a straight line and approaches 100% very sharply at some point. The TTT results tend to confirm this. That's why I guessed a rating number that was quite a bit smaller.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #23 on: Aug 3rd, 2008, 11:54pm » |
Quote Modify
|
Recently I was looking at some rating lists for chess programs.
http://en.wikipedia.org/wiki/Chess_Engines_rating_lists
Some rating lists include the bots rating along with what percent of the games it played were draws. The different playing style causes different bots of even the same skill level to have pretty wide range of draw percentages. However it seemed like there was a trend towards higher percentage of draws as the ratings increased. I pulled the data into a spread sheet and looked at a scatter plot of rating (x axis) vs draw percentage (y axis).
http://arimaa.com/arimaa/rating/ChessDrawPerc.xls
Look on sheet2 and sheet3.
It sure looks like computer programs are drawing more often as their ratings increase. Since these are computers playing, I don't think any of the games on which this data is based were early unfought draws.
Sheet 1 has data of rating vs draw percentage for human players. At a rating of around 2500 humans have a draw percentage of about 45% while computers rated 2500 are at 30%.
I had previously tried to guess the rating of a perfect chess player based on human game data and came up with a rating of about 3700. After looking at the computer data I would want to increase that guess to about 4000 to 4500.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Rating of a perfect chess player
« Reply #24 on: Aug 4th, 2008, 6:25am » |
Quote Modify
|
on Aug 3rd, 2008, 11:54pm, omar wrote:| Sheet 1 has data of rating vs draw percentage for human players. At a rating of around 2500 humans have a draw percentage of about 45% while computers rated 2500 are at 30%. |
|
If I'm not mistaken, you are comparing data from different methodologies. In your HvH data you restricted the games to ones played within a hundred point rating range. For the computers, it looks like the drawing percentage is among all games (including unequal games) that the computer plays. The inclusion of unequal games will naturally lower the drawing percentage.
Still, it is interesting that computers are forging right on past human skill level without drawing all the time. It seems we weren't as close to perfect chess as we thought.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #25 on: Aug 4th, 2008, 7:43am » |
Quote Modify
|
on Aug 4th, 2008, 6:25am, Fritzlein wrote:
If I'm not mistaken, you are comparing data from different methodologies. In your HvH data you restricted the games to ones played within a hundred point rating range. For the computers, it looks like the drawing percentage is among all games (including unequal games) that the computer plays. The inclusion of unequal games will naturally lower the drawing percentage.
|
|
Good point. Maybe that is what's causing the computer draw percentages to be lower. Perhaps the computer draw percentages would also be higher if only game between closely rated programs were considered. Before you mentioned this I was thinking it might be due only to humans more easily offering draws. Perhaps it's a combination of both. So maybe I'll stay conservative and guess at 4000 
Quote:
Still, it is interesting that computers are forging right on past human skill level without drawing all the time. It seems we weren't as close to perfect chess as we thought.
|
|
Yes, it is interesting to think that there are still many levels of unexplored depth in even a game like chess which has been so throughly studied. With Moore's law expected to continue until at least 2020, we definitely can expect even todays programs to keep forging ahead. With even a 25 rating point increase per year the best programs should be reaching 3300 by 2020. It makes me wonder if humans will be able to keep up by learning from the computers or hit some upper limit of human thinking capacity.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Rating of a perfect chess player
« Reply #26 on: Aug 4th, 2008, 8:06am » |
Quote Modify
|
on Aug 4th, 2008, 7:43am, omar wrote:| It makes me wonder if humans will be able to keep up by learning from the computers or hit some upper limit of human thinking capacity. |
|
I thought it was already clear that humans aren't able to keep up at chess by learning from computers. I wonder whether computer chess will start to be something we are bored by, like we are by computers calculating a billion digits of pi. But maybe we will still want computer chess engines around to provide accurate commentary on grandmaster games.
By the way, should we move this thread to "off-topic" ?
|
| « Last Edit: Aug 4th, 2008, 8:07am by Fritzlein » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Rating of a perfect chess player
« Reply #27 on: Aug 4th, 2008, 5:39pm » |
Quote Modify
|
on Aug 4th, 2008, 8:06am, Fritzlein wrote:
I thought it was already clear that humans aren't able to keep up at chess by learning from computers.
|
|
Really I didn't know that. I knew that in end games humans could not keep up because some know sequences are too long and bazaar to memorize and don't lend to any guiding principles, but I thought there might be more we could learn from computers in the middle game. But maybe not.
If humans had some upper limit in their thinking capacity and computers continued to march on then it could be said that chess has more depth than can ever be explored by the human mind (or perhaps I should say the unaltered human mind ). Quite amazing.
I would expect that in comparing two games which are both much deeper than can be explored by the human mind we would see the same number of levels (or ranks) attained by humans in both games. For example if 19x19 go had 30 human ranks than I would expect 23x23 go to also have the same (if it were played as much). But there is a big difference in the number of human ranks between chess and go. 30 for go compared to only 13 for chess.
http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=other;action=display;n um=1144819081;start=2#2
I am wonder what is causing this big difference. Both games have been around for a long time and have very large player pools; so humans are probably approaching their limits in both games. Could the difference be due to chess having a high draw percentage?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Rating of a perfect chess player
« Reply #28 on: Aug 4th, 2008, 8:01pm » |
Quote Modify
|
I am sure 23x23 Go would have more human ranks than 19x19 Go. Part of the reason that 19x19 Go has so many ranks in the first place is that there are about two hundred moves per game. That means there are many, many opportunities for the stronger player to outdo the weaker player. Since 23x23 Go would last almost three hundred moves, even finer distinctions in skill would translate into ranks of depth.
I think the drawishness of chess does indeed crimp its depth as measured in Elo points. If we define rank as a 75% chance of winning, then we can guess how the scale would expand if chess were drawless. Between chess players who have 50% draws, but the better player wins 75% of the decisive games, it comes out to a 62.5% score, or only 89 Elo points difference instead of 191 Elo points different. So the upper end of the chess range would probably expand to have twice as many ranks if draws were eliminated. The lower end of the chess rating scale would expand less because draws are less frequent there, but it too would expand somewhat.
Go, meanwhile, has bent over backwards to prevent draws. Not only is there a ko rule to forbid undoing the opponent's move, there is a superko rule to prevent complex cycles of repetition. Furthermore, since the scoring is in integers, the komi (point handicap) given to the second player always includes a half-point so the game can't end tied on score.
All in all, I think the assertion that Go is deeper than chess is a bit overblown. Go might be more subtle and amenable to deep insights of the human mind than chess is, but the measuring stick of ranks of depth is not as precise as we pretend.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Rating of a perfect chess player
« Reply #29 on: Aug 4th, 2008, 9:17pm » |
Quote Modify
|
on Aug 4th, 2008, 8:01pm, Fritzlein wrote:| I am sure 23x23 Go would have more human ranks than 19x19 Go. |
|
I contest the flat-out boldness of this statement. It's my understanding that 19x19 Go may possibly be optimal in the sense that it demands the greatest finesse from a human player and thus exhibit the largest human skill depth possible, if not of all known games, then at least of all the differently-sized Go versions. This, on account of the fact that on a 19x19 board the balance between territory and influence is the most ideal.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print