Author: Robert Hyatt
Date: 08:26:11 02/18/02
Go up one level in this thread
On February 17, 2002 at 17:06:04, Christophe Theron wrote: >On February 17, 2002 at 14:24:31, Uri Blass wrote: > >>On February 17, 2002 at 13:07:07, Christophe Theron wrote: >> >>>On February 17, 2002 at 11:42:47, Uri Blass wrote: >>> >>>>This game was one of the games of my program against tscp under winboard. >>>> >>>>Tscp blundered with 64...Qc4 >>>> >>>>[Event "Computer chess game"] >>>>[Site "URI-PC"] >>>>[Date "2002.02.17"] >>>>[Round "-"] >>>>[White "movei005"] >>>>[Black "tscp"] >>>>[Result "*"] >>>>[TimeControl "40/60"] >>>> >>>>1. Nc3 Nc6 2. Nf3 d5 3. d4 Nf6 4. Bf4 e6 5. e3 Bb4 6. Bd3 O-O 7. O-O Bxc3 >>>>8. bxc3 Bd7 9. Bg5 h6 10. Bxf6 Qxf6 11. e4 dxe4 12. Bxe4 Rfd8 13. Qd3 Kh8 >>>>14. h4 Rab8 15. h5 Qf4 16. Bxc6 Bxc6 17. Ne5 Rd6 18. g3 Qf6 19. a4 Kg8 20. >>>>a5 Qg5 21. Qd1 Be4 22. Qe2 Qf5 23. g4 Qh7 24. Rfc1 a6 25. f3 Bc6 26. Rcb1 >>>>Bd7 27. Qc4 c6 28. Qc5 Rd5 29. Qa7 Rd8 30. Rxb7 Qxc2 31. Rxd7 R5xd7 32. >>>>Nxd7 Qxc3 33. Rf1 Qe3+ 34. Rf2 Qe1+ 35. Kg2 Qxa5 36. Ne5 Rf8 37. Nxc6 Qa4 >>>>38. Qd7 Qa1 39. Ne7+ Kh8 40. Qd6 Re8 41. Nc6 a5 42. d5 a4 43. dxe6 fxe6 44. >>>>Ne7 a3 45. Qxe6 Rb8 46. Rc2 Rd8 47. Rc8 Qd1 48. Qa6 Qd2+ 49. Kh3 a2 50. >>>>Ng6+ Kh7 51. Rxd8 Qxd8 52. Qxa2 Qa8 53. Qf7 Qa3 54. Qf5 Qa8 55. Kg3 Kg8 56. >>>>Ne7+ Kh8 57. Kf4 Qb8+ 58. Qe5 Qb4+ 59. Qe4 Qd6+ 60. Ke3 Qb6+ 61. Kd3 Qd6+ >>>>62. Kc4 Qa6+ 63. Kd5 Qb5+ 64. Kd6 Qc4 65. Qxc4 Kh7 66. Qg8# >>>>* >>>> >>>>[D]7k/4N1p1/3q3p/7P/2K1Q1P1/5P2/8/8 b - - 0 62 >>>> >>>>black is losing in this position but tscp lost very quickly >>>> >>>>tscp played 62...Qa6+ 63.Kd5 Qb5+ 64.Kd6 Qc4??? >>>> >>>>what happened. >>>> >>>>Qc4 is leading to exactly the same position except the fact that the white king >>>>and the black queen traded squares >>>> >>>>for tscp this is the same position so it detected it as repetition. >>>> >>>>Note that I guess that tscp is losing less than 10 elo thanks to wrong >>>>repetition detection when not detecting repetition can cost it more elo. >>>> >>>>Uri >>> >>> >>> >>>Looks like TSCP is using the old GnuChess algorithm for repetition detection. >> >>Yes >>I know it. >> >>TSCP is the only program that I read almost all of it >> >>> >>>This algorithm works by counting for each square the number of pieces that have >>>moved from or to the square since the last non revertible move (capture, castle, >>>promotion, start of game). It works most of the time but fails when the position >>>is the same except that an even number of pieces have swapped their positions. >>> >>>Note that using the hash key signature to detect repetition (as most modern >>>programs do) is much better but still prone to error (it fails on what we call >>>"hash key collisions"). >>> >>> >>> >>> Christophe >> >>I guess that hash collisions are rare enough so this is not a practical problem. >> >>My program does not use hash tables and has another function for detecting >>repetition based only on the previous irreversible moves and it is always >>correct(expect cases of a change in the castling rights or change in the >>possibility of en passant capture but it seems easy to change it. >> >>I guess that the code is not simple enough for a simple chess program (about 100 >>lines of C) so I do not suggest to use it in tscp. >> >>I guess that using it in top programs will also be a bad idea because it may >>make them slightly slower. >> >>Note that it is only a guess and I do not know how much time programs use for >>detecting repetitions because I did not learn about the way they use hash >>tables. >> >>Uri > > >It is hard to beat the hash key method in term of speed. > >You just store the hash key of each move played in your current path. On each >node, you compare the hash key of the current position with the hash keys of its >predecessors (what I call the current "path"). You stop when you encounter a non >reversible move or the beginning of the list (no repetition detected) or a >position with the same hash key (repetition detected). > >There are a few optimizations to consider when you do this in order to make it >even faster. > >I have heard that some programs use a specific hash table or a specific entry in >the standard hash table to handle this, but I doubt it can be significantly >faster than the above method. It actually is faster. But (at least in the case of parallel search) it has its own set of problems since each search thread has to have its own repetition hash table, or else each entry has to be tagged which would be a mess. The simple repetition list using hash signatures is the easiest way to do this. Much less computation than the gnuchess approach, and with _far_ fewer errors. I don't see why anyone would do it any other way when this works so efficiently and correctly... > >In practice, the vast majority of moves searched by chess programs are captures, >so the backward search of previous moves stops very quickly in most cases. > > > > Christophe
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.