Chess Rating Algorithm

Chess Rating Algorithm

ImLeftFooted

Member #3,935

October 2003

Due to an interesting turn of events, I need to calculate someones chess rating. So far I've found this description of the offical formula.

http://math.bu.edu/people/mg/ratings/rs/node1.html

Does anyone have any previous experience with this or know of somewhere I can rip code from?

How is my posting?

Evert

Member #794

November 2000

Ah, somehow I thought you were looking for a way to rate chess positions (for a chess program), which I do have some direct experience with.
From what I remember about calculating someone's performance ELO rating, it's not actually that hard, but I don't remember the details... I'm sure I have the source code to the program we used in our chess club back home (the guy who wrote it is the guy who explained to me how to do the calculation), but it's on a computer that's powered down on another continent than where I am at the moment. It probably wouldn't have been terribly useful to you anyway, since I seem to remember the code had a lot of syntactic sugar to make it look like some horrible Pascal/Bourne shell hybrid (it's C though).

sorry I couldn't be more helpful...

ImLeftFooted

Member #3,935

October 2003

Here's what I've put together based on this article:

int rating;
int opponentRating;
float score = 0;

if(win)
  score = 1;
if(draw)
  score = .5f;

rating = round(rating + 32 * (score - 1 / (1.0f + 10 * (otherRating - rating) / 400.0f)));

(This assumes a K value of 32, which is typically only used for novice games. GM games and above use K values of 10 or so. See ^[1])

Evert said:

Ah, somehow I thought you were looking for a way to rate chess positions (for a chess program), which I do have some direct experience with.

I am also very curious about that. How much time would it take me to make a decent chess program? How do I rate a chess position?

References

http://en.wikipedia.org/wiki/Elo_rating_system#Most_accurate_K-factor

How is my posting?

Evert

Member #794

November 2000

Dustin Dettmer said:

(This assumes a K value of 32, which is typically only used for novice games. GM games and above use K values of 10 or so. See [1])

The K value should depend on the number of rated games; it's higher if there are fewer games that have been rated (which is typically the case for novice players, of course).

Quote:

I am also very curious about that. How much time would it take me to make a decent chess program? How do I rate a chess position?

Writing a chess program isn't actually that hard, but writing one that plays decently... meh. I don't think I've succeeded in doing that.
The most important factor in determining how good a chess program plays is how many moves in advance it can calculate. That means the key is to make everything as fast as possible, in particular move generation (the list of possible moves) and your evaluation function. Because a chess board is 8x8=64 squares and a byte is 8 bits (and 64 bits fit exactly in a word on a modern CPU), there are some very neat and efficient bit-twiddling tricks you can use to generate moves (for instance, to generate all possible pawn moves, take a "bit board" representing pawn positions for a particular player, shift it by one row and do a logical and with a bitboard that represents all empty squares; now you just read off the non-zero bits to find possible pawn destinations). For the evaluation function too the important thing is to keep it simple. In practice, that means counting material (disappointing as that is): give a pawn a value of 100 (say) and assign the other pieces their relative increase in value (you can play around a bit with the values here: 300 could be a knight or a bishop, or you could make bishops 325 if you prefer, or give them a slightly higher value if the player still has both of them). Then it's just a matter of bookkeeping.
Once that's up, you can refine it by scoring points for pawn structure or strategic placement of pieces (near the centre of the board, attacking squares near the enemy king), that's something you can spend forever on.

Do a google for "minimax" or "alpha-beta algorithm" if you want to work out the details.

Damn, now you've made me want to write a chess program again. :-/

Inphernic

Member #1,111

March 2001

Evert said:

(for instance, to generate all possible pawn moves, take a "bit board" representing pawn positions for a particular player, shift it by one row and do a logical and with a bitboard that represents all empty squares; now you just read off the non-zero bits to find possible pawn destinations)

You'd also have to take into account en passant and that pawns can move two squares on their first move.

--
ĸoтёнoк

Evert

Member #794

November 2000

Inphernic said:

You'd also have to take into account en passant and that pawns can move two squares on their first move.

You did realise you were stating the obvious, right?
Ok, what I described gives you all possible regular pawn moves. All double pawn moves can be generated by repeating this procedure twice, all captures by shifting the bitboard by 7 or 9 bits instead of 8 (be sure to mask the column that would wrap around the board). En-passant capture requires some special care in the sense that you have to keep track of the e.p. square.

Inphernic

Member #1,111

March 2001

Evert said:

You did realise you were stating the obvious, right?

To all chess players, sure, just like offside rules in American football are obvious to those who are familiar with them.

In my experience, many casual players (even good ones) are not aware of en passant. There should be no harm done in saying that implementing method X for generating all possible pawn moves doesn't quite generate all possible pawn moves, whether Dustin is familiar with the move or not.

--
ĸoтёнoк