Tuesday, October 27, 2009

Basic Ideas in Breakthrough

First off, stop detecting my blogs as spam you silly site.

Secondly, here is the basic way I will be doing diagrams:

  1 2 3 4 5 6 7 8
A X X X X X X X X
B X X X X X X X X
C - - - - - - - -
D - - - - - - - -
E - - - - - - - -
F - - - - - - - -
G O O O O O O O O
H O O O O O O O O
'O' to move


Not flashy for sure, but very legible.

Basic Concept 1:
Runners


Definition:
A piece that can reach the goal* alone if the rest of a player's moves were devoted to

*A minor but important detail, a piece is still considered a runner if it cannot actually win the game, eg if your opponent would win before you even got there. We are simply talking about the pattern in general, without respect to the rest of the board.


Tidbit:
I thought of the term runner to describe a piece that has a clear path to victory by itself. Surprisingly the strategy section of the Zillions of Games file for Breakthrough uses this term too. I suppose this makes it the closest to official Breakthrough terminology as it is possible.


Description:
Very often in Breakthrough it helps to only consider a certain portion of a board, say for the following (contrived) position:

  1 2 3 4 5 6 7 8
A - O - O O O O O
B - - - O - - - -
C O - O O - - - -
D X O O - - - - -
E - - - - - X - -
F - - - - X - - -
G - - - - - - - -
H - - - X X X X X
'X' to move 


It is very easy to tell that the X pieces will win here. To prove that D1 is a runner we look at the critical area of that piece - that is, the possible squares the piece may reach in the remaining lifetime of the game.

  1 2 3 4 

A - O - O 
B - - -   
C O -     
D X       
'X' to move 




This in turn is a very simple problem. Notice this cuts off all the enemy pieces that could never reach our X in their lifetimes. From here, we evaluate this as if it were a small breakthrough game. The only difference is that Os have no winning goal, and can pass if they so like (representing an irrelevant move outside of this subsection). As it turns out this subsection is an easy win for our lone X runner, as he simply goes to C2, and now this is the critical section:

  1 2 3 4 

A - O - O 
B - - -   
        C   X             
'O' to move

Notice that the O on C1 becomes irrelevant. The only relevant pieces become the Os on A2 and A4, but sadly they are unable to do anything meaningful. Any move other than A2 to B2 will result in C2 to B2, and the move A2 to B2 will result in us sidestepping the piece, by C2 to B1. Either way the piece will get to the end and win the game.

If you have a winning runner, it will always be able to win in exactly the amount of moves away it is from the goal, since it continuously marches forward. In our example proving our runner proved a win in 3 moves. As every O is more than 3 squares away from our goal, we can declare this as a win in 3 for the X pieces.

Basic Concept 2: 
Row structures

Definition:

Any formation of friendly pieces that puts them side by side. The simplest row structure is two side by side pieces.

Strengths:
2 pieces side by side defend all squares diagonally and directly in front of them, making up for the fact that pieces cannot capture vertically. This makes them hard to skirt around for a runner, requiring backup often.
 
 - O O - 
    x x x x    
 
Where the bold small x's represent defended/attacked squares.

  1 2 3 4 

A - O O -
B - - - -
C - - - -
D - X - -
  The X piece cannot penetrate the defense.


An added benefit is that any piece in a row structure, when moving up one square, will be defended.

Weaknesses:
The row structure does not defend any of it's pieces.

Basic Concept 3:
Column structures


Definition:
Any formation of friendly pieces that puts them one in front of another. The simplest column formation is a piece in front of another piece.


Strengths:
Although the square in front of the front piece is unguarded, an enemy piece that lands there is 'trapped'.

  1 2 3 4 

A - O - -
B - O - -
C - O - -
D - X - -
E - X - -
Defending against two pieces with three is only possible with one X 'trapped' as shown here
 

Breakthrough: An introduction

What:
To quote wikipedia:

Breakthrough is an abstract strategy board game invented by Dan Troyka in 2000 and made available as a Zillions of Games file (ZRF). At this time it was played on a 7x7 board. It won the 2001 8x8 Game Design Competition, even though the game is trivially extendable to larger board sizes. It has some similarity to checkers, but the strategy is completely different.[1]



The rules are simple:
Each player takes turns moving a piece forward. It can move forward diagonally (left or right), or straight. Pieces can only capture diagonally (think chess pawns, except with the power to move diagonally whenever). If you get a piece to the other side, you win. Draws do not occur because pieces as a rule go closer and closer to the goal (or to their death).

This blog will mostly focus on the 8x8 version (as I believe it is the most feasible to promote, fitting on a chess or checkers board), with certain concepts trivially extended to other sizes.

Why:
There was no other resource on breakthrough strategy I could think of, and a blog was far easier than creating a site. I hope to write up on various aspects of breakthrough strategy and bring light onto this game, which follows Einstein's principle of being as simple as possible, but no simpler.

I am currently working on an AI for Breakthrough in C++.

Who:
Random anonymous person, not affiliated with the game's inventor. Not particularly experienced in the game as of yet, just hoping to publish some rudimentary theory about it to get people started. As far as I know, it is a fairly unexplored game.

Where:
There are various places to play online, usually play by mail. Ludoteka is the only site I know of that allows play in real time (with several variations available). Note that it is a Spanish website, and from my experience it is hard .
There is an implementation for Zillions of Games, which allows rudimentary online.