Tilbage til Skak


Dabbaba

NB: notation of games is often in german (= danish) in this article.

 

  • Dabbaba
  • By Jens BŠk Nielsen
  • Dabbaba is a chessprogram I have written from May 1995 to Nov. 1998. It is programmed in C and consists of 7000 lines.

    It runs on a 386 or higher IBM compatible PC and runs in DOS mode.

    On my Pentium II 233 Mhz it searches 16.000 pos./sec. and twice as much in simple endgames.

    This article will mainly focus on Dabbaba's specialities and play.

     

    Finding deep mates...

    A characteristic feature for Dabbaba is that it starts each move by using up to 20% of its allotted time on following long sequences of checks to see if it results in a mate, material gain or perhaps a saving draw.

    See the following 3 examples. You can try them out yourself before you look at the solutions.

    Diagram 1:

    5nk1/nbb2pr1/p3p1p1/1p1r3q/2P5/PP1PP1P1/N3RP1P/BQN1RBK1/b

    Black to move. Dabbaba finds a mate in 10 moves in 0.33 second (Pentium II 233 Mhz).

     

    Diagram 2:

    3nn3/2p2p1k/1p1pp1p1/p2B3p/r2B2N1/4P2N/3PKPP1/6q1/w

    Dabbaba does not play 1.Nxg1, but finds a mate in 12 moves in 0.27 second.

     

    Diagram 3:

    q7/1p2pppb/7p/1P5k/4PP1b/2P3PP/1N1N3K/6B1/w

    White could play 1.gxh4, but Dabbaba finds another move in 0.16 second that wins the black queen in 7 moves.

    Solutions:

    Diagram 1: 1.-,Dxh2+! 2.Kxh2, Th5+ 3.Lh3, Txh3+ 4.Kxh3, Th7+ 5.Kg4,f5+ 6.Kg5, Ld8+ 7.Kf4, g5+ 8.Ke5, Sc6+ 9.Kd6, Lc7+ 10.Kc5, Sd7+ mate.

    (If you use quiet moves, the position is really a mate in 8 moves)

    Diagram 2: 1.Sg5+, Kg8 2.Sh6+, Kf8 3.Sh7+, Ke7 4.Sg8+, Kd7 5.Sf8+, Kc8 6.Se7+, Kb8 7.Sd7+, Ka7 8.Sc8+, Ka6 9.Sb8+, Kb5 10.Sa7+, Kb4 11.Sa6+, Ka3 12.Sb5+ mate.

    Diagram 3: 1.g4+!, Kg6 2.f5+, Kg5 3.Le3+, Kf6 4.e5+!, Kxe5 5.Sbc4+, Kd5 6.Sb6+ and 7.Sxa8

    Genius 5 uses more time to understand, that the moves lead to mate: 12 seconds for diagram 1, and 23 seconds for diagram 2. Not because Dabbaba is better or compareable to Genius 5, but because Genius 5 doesn't bother to search lines as deep as Dabbaba does. It is probably considered as waste of time to search that deep in usual play.

    But I find it attractive that Dabbaba may find a very deep combination.

     

    How does Dabbaba find these combinations?

    It is easy to follow these lines of checks. The problem is to avoid, that the varianttree explodes. I have allowed Dabbaba to use up to 20% of its time for a move in this search, that I call the matesearch (it is programmed as ’iteration 0’).

    If Dabbaba has 60 seconds for a move and searches 16.000 pos/sec, it is allowed 20/100 * 60 * 16.000 = 192.000 nodes in the matesearch.

    If that is exceeded Dabbaba simply stops the matesearch and continues with the normal search.

    But this is much too simple. Dabbaba would probably still only be examining the first move, that easily results in millions of checks.

    I have done two things to avoid this. First I allow fewer checks to be examined, the deeper you go. For the second I do it in a dynamic way, that also considers how many moves the defender have. The effect is, that shallow lines are searched deeper than wide lines.

    Before I explain this in detail I must teel, that Dabbaba generates all moves at each node and gives them a quick evaluation, so it first tries attractive moves as capturing big men or moving attacked men.

    At the top of the tree I set the fictive ressource mate_sch_pos[0]=16000, and at the top level all checks are tried. In diagram 2 white has two checks: 1.Sg5+ and 1.Sf6+. So mate_sch_pos[0] is divided by 2 giving mate_sch_pos[1]=8000. Whites first move tried is probably 1.Sf6+, as Sg4 is attacked by a pawn. After 1.Sf6+ black can escape check with 4 moves, so mate_sch_pos[1] is divided by 4 giving mate_sch_pos[2] = 8000/4 = 2000.

    Now this value is used to determine, how many checks white is allowed to try:

    Mate_sch_pos[x] number of moves

    < 2 0

    < 1000 1

    < 1.000.000 2

    White is still allowed to try 2 moves etc.

    This selektion of checks means naturally, that Dabbaba won’t find a mate if there is an unlikely check among other more likely checks along a line.

    But Dabbaba does find many combinations. The above 3 examples are taken from the file matesrch.epd, where many other examples can be found.

    Dabbaba actually performs the matesearch 3 times to the depths 8 ply, 16 ply and 24 ply. I am still a little afraid, that it will miss some power for the last moves and thereby miss a simple mate if I start out with a 24 ply search. I must check this some day. . .

    Another rule is, that a new matesearch won’t be started if more than 1/3 of the allowed nodes already have been searched.

    In simple positions mores nodes are searched pr. second, so Dabbaba may make a new estimate on the allowed nodes if the previous matesearch(es) has lasted for more than 0.20 second. This is required to make the calculation reliable.

    Diagram 3 requires something extra, as 7.Sxa8 is not a check. Such moves that may result in a better material balance than in the initial position may also be tried. To save time black is only allowed recapturing moves and checks.

    Here the matesearch did not result in a mate, so Dabbaba continues with the usual search trying to find a better move than the matesearch found. So Dabbaba trusts in 1.g4+ although not all of blacks moves after 7.Sxa8 were examined. Therefore are moves like 7.Sxa8 typically only tried beyond ply 10, as the usual search will check the move within 10 ply anyway and even more properly.

    If you want to program something similar like this matesearch, be aware to measure and consider the speed of the computer your program uses.

    Mate_sch_pos[0] is actually initialised to 8000 + (100 * speedfactor), where the speedfactor is 10 for a 50 Mhz 486 (my old PC). And the allowed number of nodes etc. must also consider the speedfactor.

     

    Dabbaba's play...

    In autumn 1997 Dabbaba participated for the first time in a tournament, where 23 programs and Torsten Schoop played 9 rounds.

    Torsten Schoop ran on his two Pentium 133Mhz the whole tournament alone! The games were played at 60 moves in 60 minutes.

    Dabbaba scored 3/9, and it played a nice game against PAX.

    [Event "Quali97"]

    [Site "60/60"]

    [Date "1997.08.11"]

    [Round "6"]

    [White "Dabbaba 051197"]

    [Black "PAX 0.0001L "]

    [Result "1-0"]

    1. e4 c5

    2. Sf3 d6

    3. d4 cxd4 {*}

    4. Lb5+ Ld7

    5. Sxd4 Sf6

    6. Sd2 e6

    7. O-O d5

    Dabbaba plays very well in this game; in fact all the

    rest of its moves is identical to the moves Genius2

    proposes in an analysis of the game!

    8. exd5 e5?

    9. Te1 Dc7

    10. S2f3 e4?

    11. Lg5 a6(?)

    12. Lxf6 gxf6

    13. Txe4+ Kd8 (worse were 13.-,Le7 14.Sf5)

    14. Lxd7 Kxd7? (Genius2: 14.-,Sxd7 15.De2,Ld6 16.Te1,Se5)

    15. c3 (with the nasty threat 16.Da4+,b5 17.Sxb5)

    15. - Dc4? (Genius2: 15.-,Kd8 15.De2,Ld6 16.Te1,Dd7)

    The log shows, that Dabbaba after 49 seconds understood it

    could improve its score from 4 pawns to 7 pawns by the

    move...

    16. Se5+! fxe5

    17. Dg4+ Kd6?

    Makes it easier for white, but whatever black does, he

    loses the queen as the knight moves with a check and the

    rook can capture the queen:

    17.-,f5 18.Dxf5+,Ke8/Kd6 19.Dxe5+,Kd7 20.De8+ followed by check with the knight

    19.-,Kf7 20.De6+,Kg7 followed by 21.Tg4+ mate.

    17.-,Ke8 18.Sc6!! with the threats Txc4/Dc8+ mate. (18.Txe5 is also good)

    18. Sf5+ Kc7

    19. Txc4+ Kd8?

    20. Dg5+ Ke8?

    21. Tc8+

    PAX resigns because of 22.Dd8+ mate.

    During this tournament and afterwards Torsten Schoop has been very, very helpfull with e-mails, information, hints, files and many games played with auto232 mainly against Diogenes.

     

    Dabbabas current strength...

    Dabbaba has improved much since this first tournament and its first presentation in Computer Schach & Spiele 3 1998. It has now got permanent brain, hashtables (although small; 2.048 entries), improved openingplay and now it knows all the rules for draw.

    I estimate its rating now to 1.900 on a fast pentium.

    Two matches have been played against humans; each with a rating ca. 2.000.

    4 games were played in each match, and each player got 15 minutes for the whole game. Dabbaba only got 8 minutes, as I should use 7 minutes to transfer the moves.

    Dabbaba won 5-3 although the humans had the best position in most of the games. The limited time put pressure on the humans, but Dabbaba also lost on time in a won position in a long game.

    Here is the first game from the first match.

    [Turnier "Match 5. maj 1998. Parti nr. 1."][Wei▀ "Peter Haarup"][Schwarz "Dabbaba"][Ergebnis "0-1"]1. d4 d5 2. c4 dxc4 3. Sf3 c5 4. d5 e6 5. e4 exd5 6. exd5 b5 {this greedy move is not in Genius 5’s openinglibrary} 7. a4 Lb7 8. axb5 Dxd5 9. Dxd5 Lxd5 10. Sc3

    Lxf3 11. gxf3 Sf6 12. Lxc4 {Peter got his pawn back and Genius 5 gives him an advantage of a half pawn} Sbd7 13. Sd5 Ld6 14. b6 a5 15. Sxf6+

    Sxf6 16. Lb5+ Ke7 17. Ld2

     

    17. -,Thb8 {according to Genius 5 black starts to get an advantage here although it almost disappears around move 22. The most important is, that the complications here made Peter use a good part of his time...}

    18. Lc6 Ta6 19. Lxa5 Tbxb6 20. Le4 Lc7 21. O-O Txa5 22. Txa5 Sxe4

    23. Ta7 Sd2 24. Txc7+ Kd8 25. Td1 Tg6+ 26. Kh1 Kxc7 27. Txd2 Td6

    28. Tc2 Td1+ 29. Kg2 Kd6 30. Kg3 h5 31. h4 g6 32. f4 Tg1+ 33. Kf3

    Tg4 34. b4 cxb4 35. Tb2 {b2-b4 was bad, but with this move black easily keeps his pawn. 35.Tc4,b3 36.Tb4,Txh4 and white still cannot recapture the pawn because of -,Th3+} Kc5 36. Ke3 Txh4 37. Tc2+ Kd6 {-,Kb5 must be the right move} 38. Tc4 b3 39. Tb4 Th3+ {-,g5! should be played here}

    40. f3 Th1 41. Txb3 Te1+ 42. Kf2 Tc1 43. Tb5 h4 44. Kg2 Tc4 45. f5 {the idea is good, but were much better if white first played 45.Tb6+,Ke7}

    g5 46. f6 Tc5 47. Tb6+ Ke5 48. Kh3 Tc4 49. Ta6 Tb4 50. Tc6 Tf4

    51. Kg2 Txf6 52. Tc5+ Kf4 53. Tc4+ Ke3 54. Te4+ Kd3 55. Tg4 Tf5

    56. f4 f6

    White lost on time.

     

    Another example is from the auto232-games against Diogenes. Dabbaba usually looses, but sometimes it wins. Here it performs a nice kingattack chasing Diogenes king to f4 at move 28.

    [Turnier "Dab_Dio, 60/60, P-120"]

    [Datum "1998"]

    [Wei▀ "Dabbaba 060598"]

    [Schwarz "Diogenes 4.61"]

    [Ergebnis "1-0"]

    1. e4 e6 2. d4 d5 {*} 3. Ld3 {Dabbaba has no openingbook...} dxe4

    4. Lxe4 Sf6 5. Lg5?! {better were Le4-d3 } Le7?! {Diogenes should

    play c7-c5} 6. Lf3 h6?! 7. Lh4 g5?! {black weakens his kingside.

    Better were still c7-c5} 8. Lg3 O-O?! {Will Diogenes never play c7-c5

    in this game?} 9. h4! c5? {at last c7-c5 came, but now Nf6-d5 were

    better} 10. hxg5 hxg5 11. dxc5?! {better were probably Qd1-d2, but

    although the queens now are exchanged, Dabbaba gets a strong

    kingattack} Dxd1+ 12. Lxd1 Lxc5 13. Sc3? Td8? {black should now play

    Bc5-b4. White should have played the knight to d2, so c2-c3 was

    possible } 14. Sf3 Sh7 15. Le5 Le7 16. Lc7 Te8 17. Le2 Sc6 18. O-O-O

    g4 19. Sd2 Sf6 20. Sc4 Lb4 21. Sb5 e5 22. Scd6 Te7 23. c3 Lc5

    24. Th6! Se8? {giving white knight and bishop for a rook with Kg8-g7

    were better} 25. Tdh1! Kg7? {now Lc5 gets lost. Only 3 moves later

    Diogenes king is at f4!} 26. Th7+ Kf6 {if the king goes back, Se8 is

    lost. The rest of the game is a safe win by Dabbaba} 27. T1h6+ Kg5

    28. Se4+ Kf4 29. Sxc5 Kg5 30. Th5+ Kg6 31. Ld6 Sxd6 32. Sxd6 f5

    33. T7h6+ Kg7 34. Kd2 Sd8 35. Th7+ Kf6 36. Th8 Kg6 37. Th2 g3

    38. T2h3 Sf7 39. Sxc8 Sxh8 40. Sxe7+ Kf7 41. Th7+ Kf6 42. f3 b6

    43. Sd7+ Ke6 44. Sc6 Sg6 45. Sdxe5 Sxe5 46. Th6+ Kd7 47. Sxe5+ Kc7

    48. Ke3 a6 49. Kf4 b5 50. Ld3 Kb7 51. Sd7 Tc8 52. Lxf5 Ka7 53. Th7

    Td8 54. Sc5+ Kb6 55. b4 a5 56. a3 axb4 57. axb4 Tb8 58. Tf7 Te8

    59. Tb7+ Kc6 60. Ld7+ Kd5 61. Lxe8 Kc4 62. Se4 Kb3 63. Td7 Kb2

    64. Td2+ Kc1 65. Lg6 Kb1 66. Sc5+ Kc1 67. Sb3+ mate

     

    Playing variants of chess...

    Another special feature of Dabbaba is that it besides orthodox chess can play 11 variants of chess.

    The first is Stationary Chess, where the kings simply cannot move.

    Here is a complete game played by Dabbaba against itself with only 10 seconds pr. move. With this fast tempo on my old 486 there are naturally a number of errors, but the game is filled with matethreats and is quite amusing.

    1.Sf3 Sf6 2.Se5 e6 3.Sxf7 De7 4.Sxh8 Se4 black now uses the same strategy as white, but white forgets to give his queen some air

    5.Sc3? Sxf2 6.Sb5 Dc5? black should play 6.-,Sa6. Now white gets air for his queen with tempo.

    7.d4 Dxb5 8.e4 Db4+ 9.Ld2 Sxd1 10.Lxb4 Se3 threats mate on c2

    11.Tc1 Lxb4+ 12.c3 Le7 threats 13.-,Sxg2+ 14.Lxg2, Lh4+ mate

    13.Tg1 Lg5 14.Ld3 if now 14.-,Sxg2 15.Txg2, Lxc1 16.Tf2! and white wins

     

    14...e5? black should develop his queenside. This move weakens his king.

    15.g3 Sc4 threats 16.-,Ld2+ mate

    16.Tc2 Ld2+ 17.Txd2 Sxd2 18.Le2 g6 avoids 19.Lh5+, g6 20.Tf1!, Sxf1 21.Sxg6!

    19.dxe5 Sc6 20.Tg2 Sxe4 prevents white from 21.Tf2 and 22.Tf8+ mate

    21.Sf7 Se7 22.Ld3 Sc5 23.Lc4 Sf5 24.g4 b5 black is in trouble now. He cannot move Sf5 because of 25.Sd6+, cxd6 26.Lf7+ mate

    25.Lxb5 Sh4 threats mate on g2 and f3

    26.Tf2 Se6 covers f8, where white would mate after 27.Sd6+, cxd6 28.Tf8+ mate.

    27.Lc4! Sf5 blacks position is hopeless now

    28.Sh6 Sg5

    29.Lf7+! Sxf7 30.Sg8 Sxe5 31.Sf6+ mate.

     

    Another of Dabbabas chess variants is Nightrider Chess, where the knight can make long moves. Here is the start of a game:

    1.d4 d5 2.Se5 Lf5 3.Lf4 e6 4.e3 Lb4+! white cannot play 5.c3, Lxb1 as the nightrider is much more worth than a bishop

    5.Ke2 Ld6!

     

    White loses a nightrider now (6.Sf3, Lg4). But why couldn't Dabbaba play 6.Sg1 to save his nightrider? Because of 6.Sg1, Lxf4 7.exf4, Lxc2! followed by 8.-,Lxb1 (8.Dxc2?, Sxd4+! - oh, yes, there was a nightrider on b8!).

     

    In 4 of the variants the knight can also move like a fairy piece. One of these pieces is called a Dabbaba, and it is of course from that piece the program has got its name.

    A dabbaba moves in the same directions as a rook, but always 2 squares and it may jump over a piece.

    Here is an example from a game of Dabbaba Chess played by Dabbaba against itself:

    Nn4k1/pp3prp/8/8/4b3/6P1/PPP4P/2KR1B2/w

    17.Nc8! a6 black saved his pawn, but...

    18.Ne8+! Kh8 If 18.-,Kf8 19.Nf6+ (yes, a check) and black loses his bishop. Now the program don't play 19.Nxg7 as the knight+dabbaba is a little more worth than a rook, but it plays

    19.Nf6! Rg5 20.Nxe4

    What happened? Why didn't the program play fx 19.-,Bg6 to save the bishop?

    Because Dabbaba would have played 20.Nh6+ mate!