### Breakthrough puzzles Breakthrough

12 replies. Last post: 2011-01-12

Breakthrough puzzles
• maraca at 2010-06-12

• maraca at 2010-06-12

Okay I make the start. I was wondering how Monte Carlo performs on Breakthrough. The success is very limited, only in endgame positions the programm seems to be not too bad, but not too strong either, even after I addes some knowledge in terms of “good moves” are taken with a higher probability.

By running a simulation I found a puzzle, it's more for beginners to intermediate:

. . . . . . . .

O . . . . . O .

O O O O O O O O

O . . . O O O .

. . X . X . . .

X X X X X . X X

X . X X . . X X

Which move guarantees X to win.

. . . . . . . .

• maraca at 2010-06-12

. . . . . . . .

O . . . . . O .

O O O O O O O O

O . . . O O O .

. . X . X . . .

X X X X X . X X

X . X X . . X X

. . . . . . . .

Note: Use p style=“font-family:courier, monospace”… I hope it works.

• maraca at 2010-06-12

In 15 moves if both play “perfect” (if a loosing player can play perfect).

• maraca at 2010-06-12

And there are 2 equal winning moves, I think now I said it all ;-)

• idiot at 2010-06-12

got it. nice puzzle…

• maraca at 2010-06-12

Thanks, you are now officially the first one who solved this puzzle :-D

Hi maraca thanks for the puzzle.

I've also tried Monte-Carlo/Uct on Breakthrough, but the results were a bit disappointing. It performed worse than a naive alpha-beta with a very basic evaluation function.

Has anybody heard of a decent AI on boards >= 6x6? Decent means able to beat a beginner.

(I am not sure though, this is the right thread to discuss AI stuff…)

• maraca at 2010-06-13

Hi halabda, very interesting. I think we can discuss this here, I haven't to say too much about it ;-) I haven't heard of any decent AI, but I wasn't looking for it and if you find a good AI, please don't publish it, or breakthrough will be one of the games where people aren't playing any more. The knowledge I added was something like this: It's good to beat without getting beat after. It's good to beat in the own half of the board. The result was that the play became much more defensive (otherwise the ai would almost everytime move the peg that is the nearest to the finishing line), but still… The opening is completely hopeless.

Btw: I made a mistake, idiot found that 'O' can play better and the shortest winning path for perfect play is 17 moves and NOT 15 moves.

• maraca at 2010-06-13

8 O . . . . O O O

7 . . O O O O . .

6 O . . . . . . O

5 O X . O X X O X

4 . . . O . . . O

3 . X . X . . X X

2 . X X . . X X .

1 . . . . . . . .

- A B C D E F G H

O to move and win. Shortest winning path for perfect play: 21 moves.

I think this shows why computer programs are having problems. You have to be able to detect winning moves very early.

• maraca at 2010-06-13

Sorry, mistake again.

8 O . . . . O O O

7 O . O O O O . .

6 . . . . . . . O

5 O X . O X X O X

4 . . . O . . . O

3 . X . X . . X X

2 . X X . . X X .

1 . . . . . . . .

- A B C D E F G H

• Christian K at 2011-01-12

These puzzles are too hard :P

Anyway, my intuition in the first one says

X should move a peice from the third row form hte back.

The peice should be number 3 or 5 from the right. They should move forward in the empty space diagonally between them.

Nowhere near sure though. I had have 5ECTS points for whatever this summer

(studying computer science)

I am thinking about trying a breakthough AI. Could be pretty interesting.