|
|
|
Topic: Threefold repetition rule
| |
|
|
Author
| Message |
|---|
|
|
Yes but you're already doing most of that (1, 2, 3, 4, 5 and 7) anyway in order to make a move. And there are plenty of more efficient representations than FEN.
|
|
|
Changing from FEN to `another_method` implies in change much things...
KISS... :-)
You're already using FEN... You already have a function to generate FEN... Why would you change the entire site dynamics just for a representation?
You must analyze the "TCO"... ;-)
If the another method is simpler to read and simple to compare, let's change... Otherwise, why do that?
Did you get the point?
|
|
|
For a 50 move game, davivad's algorithm would need 49x48x3 comparisons, inefficient given the number of games going on.
The best algorithm for this (used by chess engines) is just to hash all positions for the side in the game, and keep a running count of the number:
/* in C notation */
(hash(current_pos,side)->count))++
canclaimdraw = FALSE
If hash(current_pos,side)->count >= 3
then canclaimdraw = TRUE
You still have to keep a track of the side whose turn it is to play in calculating the hash, as the same piece position with different color to play can occur in the same game. e.g. in simple pawn endgames.
For flexibility, you will probably use 2 hash functions: one that will convert the chess position with side to play to a comparable number ( say HASH1, the standard one used for chess engines, often used for the address as well).
The other, HASH2 is used to compute where in server memory (the address) where the computed HASH1 values, along with its corresponding GAME_ID and count of number of repetitions will reside.
In this case, possibly secondary or storage memory, given the large number of games, and average number of positions occurring in each game.
|
|
|
| edvz wrote: For a 50 move game, davivad's algorithm would need 49x48x3 comparisons, inefficient given the number of games going on. |
All these arguments about efficiency seem to be forgetting that this fifty-move game will probably last for two months or more. The cost of doing a few thousand string comparisons over the course of a couple of months is negligible. Even the cost of storing the data isn't all that big.
But, of course, there is more than one game. However, there have been fewer than 250,000 games in total, of which I doubt more than, say, a third are currently active. Even assuming that each game receives, on average, one move per day, that's still only about a move a second the site has to process.
I'm not suggesting that storing FENs and comparing them all is a good way to detect repetitions but all these arguments about efficiency seem to be rather missing the point. There's no point optimizing non-critical code if the code is already good enough.
|
|
|
As an upper limit then, for 100,000 thousand games at any given time, each at about 50 moves per game (100 half moves) lasting 10 weeks.
That's 1,000,000 moves per week. And using davidad's method, x 7,500, or 7.5 billion position comparisons per week on top of just servicing all the games.
That's probably okay if you've got a server to yourself, but not if you're sharing it with a 100 other folks.
|
| Previous 1 2 3 4 5 Next |
|
|
|
