Repetition detection structure.

[hgm]

Sure, when the number of pawns gets dangerously low, the probability to win drops again. A good evaluation should take account of that. With a pawn majority (and piece equality) the strategy should be aimed at creating a passer, and most of the time you won't be able to do that with too many pawns on the board. So for 8 vs 7 pawns I think trading should definitely encouraged. The search will than try to find the best way to trade (optimizing scoring for majorities, passers, etc.). If it would systematiclly avoid trading because you consider 8 vs 7 much better than 7 vs 6, you will never get anywhere, and you create problems for yourself like you see in the Shredder game above. In such cases scoring 50-move draws should just be considered a d(dangerous) kludge that sometimes works around a fundamental shortcoming in the evaluation. And especially when 2 pawns ahead, trading down to 2 vs 0 is almost always winning, as you will have 2 passers.

[wgarvin]

I can only comment about the following:
"if you ever decide to develop something truly competitive, you will also be handling the 50 move rule counter"

I disagree with it.
I think that it is better to handle the 50 move rule but I also believe that it does not improve the playing strength by many elo points so programs clearly can be competitive even without it.

Uri

I suspect that it doesn't improve playing strength much, except in that occasional game where not knowing about the rule causes your engine to break the rule and forfeit the game.

An engine not knowing about the 50 move rule or about underpromotions is a bug, not a feature. For something like micromax its an acceptable tradeoff; for a regular engine playing at IM/GM strength it isn't.

[hgm]

I am not sure how you imagine one could "break" the 50-move rule, or how one could forfeit because of it.

Note furthermore that I am not talking about an engine not knowing about the 50-move rule. Just about an engine preferring to take the draw if it could not make any progress in 50 move, rather than trusting its positive evaluation. Because it knows that on the average that makes it score better.

Why would an engine be only acceptable for playing against IM/GM when it makes decisions that it knows to be bad?

[wgarvin]

I am not sure how you imagen one could break the 50-move rule, or how one could forfeit because of it.

You're right, the opponent would claim a draw or else nothing would happen to you. I was confusing it with a different thing.

I guess it only matters if you have a position which is winnable but not before the 50-move counter comes along, and your program will not capture or push a pawn for other reasons. It still seems that the program should know about the rule, so it can claim draws under the rule if it wants to.

[hgm]

I am not sure how you imagen one could break the 50-move rule, or how one could forfeit because of it.

You're right, the opponent would claim a draw or else nothing would happen to you. I was confusing it with a different thing.

I guess it only matters if you have a position which is winnable but not before the 50-move counter comes along, and your program will not capture or push a pawn for other reasons. It still seems that the program should know about the rule, so it can claim draws under the rule if it wants to.

Oh sure, my programs do that. (If only for the reason that some tournament directors _require_ you to claim the draw (even though FIDE rules don't), or they won't allow your engine to enter the tournament.) But for that you only have to count the moves at game level, and there is no need at all to update it during the search, which is what we were talking about here.

[bob]

What, exactly, are you talking about? What am I trying to present here? Besides the fact that using a repetition list rather than a repetition hash table, both of which I have used in the past, is better from a parallel search development point of view, and no worse from a performance point of view.

So exactly how am I "guessing". You can examine my RepetitionCheck() code in the current crafty to see just how "complicated" it is. I gave some actual data showing the average loop length for that function, something you can repeat easily enough if you want to.

So, where's the guesswork? I only see cold, hard, verifiable facts from my side.

Ah, plagued by selective memory? I would think it is pretty obvious that I was referring to this:

That's stupid. If you don't want to implement all the rules of chess, that's fine. But that is not a point in your favor when comparing effort. The 50-move-rule is necessary in a chess engine if it is going to compete with IM/GM level players.

I do see a lot of speculation and guessing from your side since you don't produce any real data in this discussion to contradict mine...

Note that no real data is required to falsify your statements, as they are of a mathematical nature. So a hypothetical counterexample is good enough to expose them as nonsense.

Let me rephrase my comment. "What exactly are you talking about?"

You claim your hash approach is more efficient than my approach. I proved my approach executes the loop exactly one time, just as your "hash loop" would do. I store an entry into a list indexed by ply. You store into a list indexed by the lower bits of the hash signature. I don't have to remove my entry, nor do any extra work whatsoever to avoid using it later in wrong positions. You do have to explicitly remove your entry or it will cause problems later.

SO, again. "what exactly are you talking about?"

That is pure crap. I have been using the 50-move rule counter approach since the late 70's, and my engine does not make random sacrifices which then lead to losses there any more than it will when trying to avoid a repetition. Repetitions are far more common. Are you saying you never sacrifice a pawn to avoid a repetition, and then lose that game? If not, why can't you do it the same way for the 50 move rule case and avoid losing those?

The major difference between the two cases is that a repetition can be recognized within the search horizon from where it starts, so that it is clear from the beginning that the engine has to choose between a repetition draw or a presumably won continuation of the game. For a 50-move draw, the engine won't get it within the horizon until after it has been trying to win the current reversible game phase by 40 moves or so, and apparently was not able to make any measurable progress in these 40 moves.

Please come back to reality. If you see a repetition in 10 plies, or you see a 50 move draw in 10 plies, the circumstances are _exactly_ the same. In either case you can claim a draw in 10 plies if you don't take some voluntary action to avoid it. There is absolutely no difference in the two. I can repeat or do something like push a pawn or capture something to clear the repetition counter. I can run into the 50 move rule draw or I can do something like push a pawn or capture something to clear the counter. There is _absolutely_ no difference in how the two affect the game, except that repetitions occur more frequently. If you handle one reasonably, you can handle the other reasonably. To suggest otherwise is ridiculous...

Now Chess is by nature an unstable game, where advantage breeds more advantage. Due to this positive feedback (true) evaluation scores tend to diverge exponentially away from equality. So if you have any real advantage at the beginning of a 40-move interval, in normal play the advantage should have amplified to material proportions (either by gaining opponent material, or bringing promotion closer). If it hasn't, this is very strong evidence that the advantage is illusory, due to misevaluation of the current position. If you are truly at +3, there is no way the opponent should be able to survive 40 moves without the score climbing to +6 or +9. If you stay at +3, the true score at the beginning cannot have been larger than +0.75 to +1.5, and by inference, it then also will be +0.75 or +1.5 when you start to see the 50-move draw looming, as nothing has changed. The eval growth over 40 moves in general is a much better indication for your true advantage than the current evaluation.

None of these arguments apply in the case of rep-draws.

All I can say is that is a nonsensical method of rationalizing a decision. A chess program has no concept of "time". An eval right _now_ is just as trustworthy as an eval that has survived for 40 moves at the same exact number. And in fact, the 40 moves at the same eval suggests that perhaps the evaluation is not correct anyway as no progress is happening. On the other hand, if I am a piece up, and making no progress, and by giving up a pawn, I can do something more, then I certainly choose to play to win when winning, not play to draw when winning.

That would seem to suggest an evaluation flaw rather than serve as a justification for not handling a rule properly.

Obviously if you do either, you have the same problem. Why not eliminate the more common occurrence of repetition avoidance rather than 50 move avoidance which is really pretty rare (where you are well ahead and have to avoid 50 move rule draws to win).

As argued above, the nature of the problem is completely different.

and as I said, they are _exactly_ the same. How can repeating in N plies for a draw be any different than just playing for 20 plies to draw? They aren't different.

Your logic completely escapes me

This, at least, is something we can agree on!

since the two cases are identical, yet you chose to accept the more frequent case and ignore the more rare one.

But as shown above, they are completely different. You don't have an eval-estimate based on progress-rate in the case of rep-draws (or stale-mates).

Please show me some code showing how your program trusts an evaluation that is high for 40 plies more than an eval that is high for 10 plies. Or vice-versa. Either the evaluation is correct and you should play for a win, or it is wrong and you should fix it. But not a kludge that ignores 50 moves. I don't see problems in how I handle it, and have seen it find creative ways to win games that might have been drawn if there was no 50 move rule to urge the program to make some sort of actual progress, rather than just holding on to a 2-3 pawn advantage and making no progress at all.

Feel free to point out a game where you beat Crafty because it did just that.

You don't think I ever study Crafty games, do you?

I actually don't think you study any games at all, based on some of these comments.

Here's a wager: I'll play a 100,000 game match on my cluster, and count the number of games where I sac a pawn and lose the game to avoid a 50 move draw, as opposed to cases where I sac a pawn to avoid drawing and go on to win the game. I'll bet the latter happens every now and then, while the former likely won't happen at all....

Want to take the test???

I think this is would be an experiment of truly fundamental importance. For that reason alone you should already do it. I don't think others are in a position to do it, as 50-move draws are rather rare. But if winning a wager is more important to you than advancing science, OK: I'll take the wager!

Play the 100,000 games, and, select all positions in those games where the reversible-move counter went up to above 80 ply, just before it was reset. (I am assuming that under your test conditions, the search will be less than 20-ply deep, so that before 80 reversible ply the 50-move barrier will be completely beyond the horizon.) Then calculate the score percentage over the selected set for the side that did the irreversible move. Preferrably take separate statistics for irreversible moves that were done with a positive score and with a negative score (or, if you use contempt, smaller and larger than contempt). We should also treat moves that have a score higher than that before the 80-ply limit, as the program would have found and played these moves without the aid of the 50-move pressure. You can take separate statistics for Crafty and for the opponents, if you want.

I wager you won't see a statistically significant positive score for the 'draw-breaker'.

First, the depth will go far beyond 20 plies in endgames, so that assumption is not so good. I have seen depths of 50 plies, particularly with just kings and pawns which is where this most often kicks in.

But your "statistically significant" leaves too much room for argument, as in 100,000 games I don't think we would see 1,000 games where this happens. What I would expect is to see some games where Crafty would win with the 50 move rule code in, and draw without it. I'll think about how to run the test so that it will play 100,000 different games rather than repeating everything as it now would with my Silver test...

[bob]

How do you select these examples? Do you have a filter to screen thousands of games for long sequences of reversible moves? How many games did you have to go through to find these examples? Did you also find examples in those games where the one playing the irreversible move lost? To have unbiased, and statistically meaningful data, three examples is not nearly enough, especially if it is not clear how they were selected. Picking examples illustrating one point or the other by hand is always easy; I could show you a game I plaid last week between Joker80 and TSCP Gothic where TSCP-G sacrifices a Pawn after 49 moves twice to keep the game going, only to forfeit on time because it cannot handle games of more than 200 moves, and crashed....

Note that the moves played here to avoid the 50-move draw are not exactly sacrifices, and that it is a mistery why the programs did not play them in the first place (30 moves earlier). There is no score drop when they play those moves.

Also note that the mechanism described above that my engines use to handle the fifty move rule would have caused them to play these moves much earlier. In some of the games they would even have been played before the '50-move-worry' would kick in, simply driven by the natural desire to trade down material when ahead. In the Bright case (where it is not clear to me that Bright even is ahead; deciding to avoid the draw here might be a blind gamble that happened to pay off this time), the move would be driven after the alternate evaluation kicks in, because it creates passers, and Bright's passer is more advanced than that of Naum. And passer advancement (pawn advancement in general) is awarded more in the alternative evaluation. So if the move was just not good enough to be selected as best even afer many attempts, after 30 reversible moves it would likely be upgraded enough to be selected somewhere during the remaining 20 moves.

I simply looked for long games that were not drawn of at least 120 moves
Fritz interface allow me to search for them and look game after game to see the reason of the win.
In most of these games the 50 move rule changed nothing and I chose only games when it seems that the program pushed a pawn or did something else because of the 50 move rule.

Many programs have no rule to trade pawns when they have material advantage so they need the 50 move rule to push them

trading pawns when you have material advantage is not always better
and KRP vs KBP is more often a draw relative to the case that there are more pawns so the rule of trading pawn when you have more material is not always correct.

Another example:
The following position is probably drawn when with more pawns white has better chances to win.

[D]2k5/ppr5/8/8/8/PPP5/2R5/2K5 w - - 0 1


Uri

Actually, the rule is "if you are ahead in material, trade _pieces_ but not pawns. If you are behind in material, trade pawns and not pieces." Crafty has always done this.

[Uri Blass]

How do you select these examples? Do you have a filter to screen thousands of games for long sequences of reversible moves? How many games did you have to go through to find these examples? Did you also find examples in those games where the one playing the irreversible move lost? To have unbiased, and statistically meaningful data, three examples is not nearly enough, especially if it is not clear how they were selected. Picking examples illustrating one point or the other by hand is always easy; I could show you a game I plaid last week between Joker80 and TSCP Gothic where TSCP-G sacrifices a Pawn after 49 moves twice to keep the game going, only to forfeit on time because it cannot handle games of more than 200 moves, and crashed....

Note that the moves played here to avoid the 50-move draw are not exactly sacrifices, and that it is a mistery why the programs did not play them in the first place (30 moves earlier). There is no score drop when they play those moves.

Also note that the mechanism described above that my engines use to handle the fifty move rule would have caused them to play these moves much earlier. In some of the games they would even have been played before the '50-move-worry' would kick in, simply driven by the natural desire to trade down material when ahead. In the Bright case (where it is not clear to me that Bright even is ahead; deciding to avoid the draw here might be a blind gamble that happened to pay off this time), the move would be driven after the alternate evaluation kicks in, because it creates passers, and Bright's passer is more advanced than that of Naum. And passer advancement (pawn advancement in general) is awarded more in the alternative evaluation. So if the move was just not good enough to be selected as best even afer many attempts, after 30 reversible moves it would likely be upgraded enough to be selected somewhere during the remaining 20 moves.

I simply looked for long games that were not drawn of at least 120 moves
Fritz interface allow me to search for them and look game after game to see the reason of the win.
In most of these games the 50 move rule changed nothing and I chose only games when it seems that the program pushed a pawn or did something else because of the 50 move rule.

Many programs have no rule to trade pawns when they have material advantage so they need the 50 move rule to push them

trading pawns when you have material advantage is not always better
and KRP vs KBP is more often a draw relative to the case that there are more pawns so the rule of trading pawn when you have more material is not always correct.

Another example:
The following position is probably drawn when with more pawns white has better chances to win.

[D]2k5/ppr5/8/8/8/PPP5/2R5/2K5 w - - 0 1


Uri

Actually, the rule is "if you are ahead in material, trade _pieces_ but not pawns. If you are behind in material, trade pawns and not pieces." Crafty has always done this.

I think that this rule is too simple to be correct.

I think that with one pawn advantage it is good not to trade pawns if you have 4 pawns vs 3 pawns but if you have 8 pawns vs 7 pawns it is the opposite.

Uri

[bob]

How do you select these examples? Do you have a filter to screen thousands of games for long sequences of reversible moves? How many games did you have to go through to find these examples? Did you also find examples in those games where the one playing the irreversible move lost? To have unbiased, and statistically meaningful data, three examples is not nearly enough, especially if it is not clear how they were selected. Picking examples illustrating one point or the other by hand is always easy; I could show you a game I plaid last week between Joker80 and TSCP Gothic where TSCP-G sacrifices a Pawn after 49 moves twice to keep the game going, only to forfeit on time because it cannot handle games of more than 200 moves, and crashed....

Note that the moves played here to avoid the 50-move draw are not exactly sacrifices, and that it is a mistery why the programs did not play them in the first place (30 moves earlier). There is no score drop when they play those moves.

Also note that the mechanism described above that my engines use to handle the fifty move rule would have caused them to play these moves much earlier. In some of the games they would even have been played before the '50-move-worry' would kick in, simply driven by the natural desire to trade down material when ahead. In the Bright case (where it is not clear to me that Bright even is ahead; deciding to avoid the draw here might be a blind gamble that happened to pay off this time), the move would be driven after the alternate evaluation kicks in, because it creates passers, and Bright's passer is more advanced than that of Naum. And passer advancement (pawn advancement in general) is awarded more in the alternative evaluation. So if the move was just not good enough to be selected as best even afer many attempts, after 30 reversible moves it would likely be upgraded enough to be selected somewhere during the remaining 20 moves.

I simply looked for long games that were not drawn of at least 120 moves
Fritz interface allow me to search for them and look game after game to see the reason of the win.
In most of these games the 50 move rule changed nothing and I chose only games when it seems that the program pushed a pawn or did something else because of the 50 move rule.

Many programs have no rule to trade pawns when they have material advantage so they need the 50 move rule to push them

trading pawns when you have material advantage is not always better
and KRP vs KBP is more often a draw relative to the case that there are more pawns so the rule of trading pawn when you have more material is not always correct.

Another example:
The following position is probably drawn when with more pawns white has better chances to win.

[D]2k5/ppr5/8/8/8/PPP5/2R5/2K5 w - - 0 1


Uri

Actually, the rule is "if you are ahead in material, trade _pieces_ but not pawns. If you are behind in material, trade pawns and not pieces." Crafty has always done this.

I think that this rule is too simple to be correct.

I think that with one pawn advantage it is good not to trade pawns if you have 4 pawns vs 3 pawns but if you have 8 pawns vs 7 pawns it is the opposite.

Uri

I don't think it matters, but for a one pawn advantage the material advantage is very small anyway. But if I am a knight ahead, with an 8 vs 8 pawn count, I am going to trade pieces whenever possible, as my knight will then be able to win other pawns easily. Where if I trade pawns, every pawn that comes off makes it that much more drawish, until all 8 are traded and we are dead drawn.

That's where the rule comes from, it's in many of my chess books. Crafty has always hated to have 8 vs 8, because it is too easy to block them up, but beyond that, it follows the above which works pretty well. I'm sure there are exceptions, but there are more examples where it is right than where it is wrong...

[bob]

Seems to me you are trying to argue that white is black, here. Your last statement is just plain nonsense: perhaps the return can be small, but the return on investment can be infinite if the investment is infinitesimal. So the "regardless the investment" does not belong there.

I am just following standard software development practice, which says to spend time optimizing the parts of the program that consume the most compute cycles, _not_ the ones that consume fractions of a percentage point. This has always been, and will always be the sane way to optimize programs...

I have no idea why you don't get that. Fortunately, most of the rest of the programming world does. Feel free to show me a quote from any programming book that would suggest rewriting and debugging a procedure that takes 0.5% of tht total execution time, when there are other procedures that take 30% and up...

My comments about it.

When I agree that it is not always good to spend time on parts that take more time because the investment is also important I still think that I will not spend significant time about making the program 0.5% faster.

speed is not everything and there are better things to do then to look for every small speed improvement that you can get.

It may be better to optimize a part that takes 20% of the time and not to optimize a part that takes 30% of the time because the job of optimizing the part that takes 30% of the time is harder but I think that it is better not to care at all about part that takes 0.5% of the time unless there are many parts like that and I do not think that chess programs has many parts that take 0.5% of the time.

Another point is that I am not sure if it is possible to give percentage of the time that the program does task X because it is possible that the program does task X and task Y at the same time and cannot continue from task X to the next task before finishing task Y.

In that case if task Y takes more time than task X you will not get a speed improvement for making task X faster so it may be better to optimize task Y first.

Uri

Uri:

This entire discussion is ridiculous. "how to optimize" is well known, references to Amdahl's law abound in the literature, and anyone that is really proficient in computer programming knows how to do this. No, you don't optimize a 0.5% module first, second, or anything else, until you take care of the ones above it. For every program there is an optimal algorithm, and eventually you will reach the point where you have done all you can do to the big parts. And then moving down to the 0.5% module is even more pointless.

I have no idea why HGM wants to get into these discussions, other than to argue. This is a cycle that repates every now and then, just like the 50 move rule draw discussion, hashing vs replist discussion, etc...

but I suppose the argument will go on... and on...