5x5 solved Breakthrough

24 replies. Last post: 2010-04-09

Reply to this topic Return to forum

5x5 solved
  • Tasmanian Devil at 2006-12-03

    I have written a java program that completely solves Breakthrough on a 5x5 board. It is based upon my analysis programs for Neutreeko, Teeko and Dao (available on my home page).

    Starting with 2 full rows each is a win for Black (the second player) in 26 moves (13 moves by each side).

    The program only keeps track of positions where neither side has advanced to the second-last row. This saves a considerable amount of memory space, but makes the algorithm more complicated, since it is sometimes necessary to “look ahead two moves at the same time”. Among these, the maximal depth was 30 moves.

    The current (early) version doesn't actually allow the user to make any moves, since I would have to work around the problem that arises when someone does advance to the second-last row. I can only type in a position, and the program tells me how many moves remain under perfect play.

    Working out the perfect opening was therefore a bit tedious, but it appears to be 1. a2-a3 (or e2-e3), 2. b4xa3, 3. b2xa3, 4. b5-b4. a1-b2 and a3xb4 are equally good 5th moves.

    I'm afraid I can't accept challenges in the forum, since the program takes 1 hour to calculate all positions before I can start analyzing. (Otherwise I would not have revealed the perfect opening right away.)

    Hopefully I can make the program more user-friendly in due course, but it's hard to find time to work on it, so I am not giving myself any deadline.

  • Carroll at 2006-12-04

    Nice work and nice to share with us the best opening line!

    Would you say this type of opening may generalize to bigger boards with two rows each ?

    Yes please find time to make a playable version, even if not an oracle.

    Could you not use it to test heuristics for an evaluation function ?

  • Tasmanian Devil at 2006-12-04

    I am too weak at the game to guess the implications for larger boards. I hope to find the time to make a user-friendly program around Christmas, if not sooner.

  • Carroll at 2006-12-07

    Could your program allow you to do 3x8 (8 vertical), I have always been skeptical about center moves…

    This is only 24 with 12 pawns and you have done 25 with 20 pawns !

  • Tasmanian Devil at 2006-12-07

    I have done a bit of improving and debugging the last few evenings and hope to “release” an OK version this evening. The idea is that you start with two full rows each, get a list of the value of each of the possible moves, and then choose one of the moves. At any time you can go back to start or enter a new position. (My other programs have a “retract last move” option that I plan to implement later.)

    In principle, only the board size matters, not the number of pawns, as the program considers all possible positions with each square either containing friendly pawn, opponent pawn or being empty. However, it only keeps track of positions with no pawns in the last two rows, which gives 220 x 35 = 254,803,968 positions on 5x5, but 212 x 312 = 2,176,782,336 positions on 3x8, since there are far more squares with 3 possibilies. In view of that, a 3x8 version would be extremely slow, if I can make it work at all.

  • Tasmanian Devil at 2006-12-07

    Correction: [The program] only keeps track of positions in which neither side has advanced to the last or second last row.

    Note that 3x7 should be OK. It only has 1/27 as many possible positions as 3x8. ;-)

  • Carroll at 2006-12-07

    In principle, only the board size matters, not the number of pawns

    I don't get it is it starting from the end, or is it Proof-number search ?

    Anyway thanks for your work, and 3x7 would be quite interesting.

  • Tasmanian Devil at 2006-12-07

    It starts by finding all positions with 3 moves remaining, then all positions with 4 moves remaining, and so on.

    A version that seems to work is now available at http://home.no.net/zamunda/neutreeko.htm. Please note the instructions for getting enough memory at the top of the file.

    I also rewrote it for 3x7 and found that the maximal depth was 38 moves, attained when the two sides have 3 full rows each, while 2 full rows each is a loss for the first player in 32 moves. However, it was still a bit buggy when I tried to make moves so it is not available quite yet.

  • Tasmanian Devil at 2006-12-08

    Bug found! Now 3x7 is available at the same page.

  • Carroll at 2006-12-08

    I will get it, thx !

    5x5 is working fine (yes you need 280MB), well counting now… 3 : 138690560 means number of positions that are wins for second player ?

  • Tasmanian Devil at 2006-12-08

    3 means win for first player in 3 moves.

  • Carroll at 2006-12-08

    A nice one that I found with 5x5 :

    Black to move and win in 13 :

     +---+---+---+---+---+5|   | x | x | x | x | +---+---+---+---+---+4| x |   |   |   |   | +---+---+---+---+---+3| x |   | o | o | x | +---+---+---+---+---+2| o |   |   |   | o | +---+---+---+---+---+1| o | o |   |   | o | +---+---+---+---+---+   A   B   C   D   E
    

    Do the specialists find it easy ?

    (One solution)

  • Carroll at 2006-12-08

    Hum, Black is X!

  • Carroll at 2006-12-08

    Couldn't you use a L/R symetry principle to remove a lot of positions ?

    Or would that be too time consuming ?

    Or maybe only for the 3-away positions, pruning all the symetrical ones…

  • Tasmanian Devil at 2006-12-08

    It would be possible to shorten the counting time by considering L/R symmetry yes, but I haven't taken the trouble. There's more to be saved in the other games I analyzed, where I implemented 8-fold symmetry. Maybe I will implement it later.

  • brunbrun at 2006-12-09

    i think the solution is E5-D4 but i don't find a defensive line with 13 move, the longest defense from white give me a win for black in 11 moves

  • Chris at 2006-12-09

    brunbrun, use b1-c2 at some point! Most of the time, though, this would result in a 7-9 move win for black…if black identifies the correct starting move.

  • Chris at 2006-12-09

    blech…9-11 I meant!

  • Ray Garrison at 2006-12-10

    1.e5-d4 2.c3xd4 3.c5xd4 4. b1-c2 5. b5-b4 6.d3-c4 7. b5xc4 8. c2-d3 9. c4xd3 10. e2xd3 11. e3-e2 12. d3-c4 13. e2-d1

  • Carroll at 2006-12-11

    Sory by chess counting this is only a win in 7 whole moves, nice done brunbrun and Ray, and yes Chris, b1-c2 is used on second defensive move.

  • Tasmanian Devil at 2006-12-11

    Well, who cares about chess :-D

  • Tasmanian Devil at 2006-12-22

    I added symmetry consideration in order to speed up the calculation, but it seemed to make little difference. Then I discovered that the programs made a lot of superfluous calculations in each loop (before checking whether a position was not already counted), and by fixing that, I managed to speed them up quite considerably. A retract-last-move option has also been added. The updated versions are, of course, available at http://home.no.net/zamunda/neutreeko.htm.

  • Carroll at 2010-04-09

    To revive this thread: you can find the java programs for 5x5 and 3x7 on neutreeko.net here

    3x7 is a win for second player in 32 (half-)moves

Return to forum

Reply to this topic