board game win situation - searching algorithm

Question

I'm looking for possibly efficient algorithm to detect "win" situation in a gomoku (five-in-a-row) game, played on a 19x19 board. Win situation happens when one of the players manages to get five and NO MORE than five "stones" in a row (horizontal, diagonal or vertical).

I have the following data easily accessible:

• previous moves ("stones") of both players stored in a 2d array (can be also json notation object), with variables "B" and "W" to difference players from each other,
• "coordinates" of the incoming move (move.x, move.y),
• number of moves each player did

I'm doing it in javascript, but any solution that doesn't use low-level stuff like memory allocation nor higher-level (python) array operations would be good.

I've found similiar question ( Detect winning game in nought and crosses ), but solutions given there only refer to small boards (5x5 etc).

Answer 1

A simple to understand solution without excessive loops (only pseudocode provided, let me know if you need more explanation):

I assume your 2-d array runs like this:

board = [
   [...],
   [...],
   [...],
   ...
];

I.e. the inner arrays represent the horizontal rows of the board.

I also assume that the array is populated by "b", "w", and "x", representing black pieces, white pieces, and empty squares, respectively.

My solution is somewhat divide-and-conquer, so I've divided it into the 3 cases below. Bear with me, it may seem more complex than simply running multiple nested loops at first, but the concept is easy to understand, read, and with the right approach, quite simple to code.

Horizontal lines

Let's first consider the case of detecting a win situation ONLY if the line is horizontal - this is the easiest. First, join a row into a single string, using something like board[0].join(""). Do this for each row. You end up with an array like this:

rows = [
   "bxwwwbx...",
   "xxxwbxx...",
   "wwbbbbx...",
   ...
]

Now join THIS array, but inserting an "x" between elements to separate each row: rows.join("x").

Now you have one long string representing your board, and it's simply a matter of applying a regexp to find consecutive "w" or "b" of exactly 5 length: superString.test(/(b{5,5})|(w{5,5})/). If the test returns true you have a win situation. If not, let's move on to vertical lines.

Vertical lines

You want to reuse the above code, so create a function testRows for it. Testing for vertical lines is exactly the same process, but you want to transpose the board, so that rows become columns and columns become rows. Then you apply the same testRows function. Transposing can be done by copying values into a new 2-d array, or by writing a simple getCol function and using that within testRows.

Diagonal lines

Again, we want to reuse the `testRows' function. A diagonal such as this:

b x x x x
x b x x x
x x b x x
x x x b x
x x x x b

Can be converted to a vertical such as this:

b x x x x
b x x x
b x x
b x
b

By shifting row i by i positions. Now it's a matter of transposing and we are back at testing for horizontals. You'll need to do the same for diagonals that go the other way, but this time shift row i by length - 1 - i positions, or in your case, 18 - i positions.

Functional javascript

As a side note, my solution fits nicely with functional programming, which means that it can be quite easily coded if you have functional programming tools with you, though it's not necessary. I recommend using underscore.js as it's quite likely you'll need basic tools like map, reduce and filter in many different game algorithms. For example, my section on testing horizontal lines can be written in one line of javascript with the use of map:

_(board).map(function (row) {return row.join("")}).join("x").test(/(b{5,5})|(w{5,5})/);

Answer 2

Even though this is a really old question I want to provide my answer because I took a deeper look into this problem today and solved it in a much (much) more efficient way.

I'm using a bit board, which is used in most of the board games and engines (chess engines) due to the efficiency, to represent my field.

You can do everything you need in this game with bitwise operations.

A bit can just have 2 states (0 and 1) however what we need are 3 states e.g. p1, p2 or empty. To solve this problem we're going to have 2 boards instead, one for each player.

Another problem is that Gomoku has a lot of fields (19x19) and there is no number type that has that many bits to represent the field. We will use an array of numbers to represent each line and just use the first lsb 15bits of it.

Vertical rows

A simplified board of player 1 could look like this

000000
101100
001000
011000
000000

Lets say we want to detect 3 in a row. We take the first 3 rows(0-2) and took at them.

000000
001100
101000

With the & (AND) operator you can check if there is a 1 in every row.

var result = field[player][0] & field[player][1] & field[player][2];

In this case the result will be 0 which means no winner. Lets continue... The next step is to take rows 1-3

101100
001000
011000

Apply the AND again and that we will get is 001000. We don't have to care what number this is, just if it's 0 or not. (result != 0)

Horizontal rows

Ok now we can detect vertical rows. To detect the horizontal rows we need to save another 2 boards, again one for each player. But we need to invert x and y axis. Then we can do the same check again to detect horizontal lines. Your array would then be:

//[player][hORv][rows]
var field[2][2][19];

Diagonals :)

The trickiest part are the diagonals of course but with a simple trick you can do the same check as above. A simple board:

000000
010000
001000
000100
000000

Basically we do the same as above but before we do that we need to shift the rows. Lets say we're at row 1-3.

010000
001000
000100

The first row stays as it is. Then you shift the second row one to the left and the third 2 to the left.

var r0 = field[0][0][i];
var r1 = field[0][0][i+1] << 1;
var r2 = field[0][0][i+2] << 2;

What you will get is:

010000
010000
010000

Apply AND you can have your win detection. To get the other diagonal direction just do it again, but instead of shifting to the left <<, shift to the right >>

I hopes this helps someone.

Answer 3

untested:

int left = max(0, move.x-5), right = min(width-1, move.x+5), top = max(0, move.y-5), bottom = min(width-1, move.y+5);    
// check the primary diagonal (top-left to bottom-right)
for (int x = left, y = top; x <= right && y <= bottom; x++, y++) {
    for (int count = 0; x <= right && y <= bottom && stones[x][y] == lastPlayer; x++, y++, count++) {
        if (count >= 5) return true;
    }
}
// check the secondary diagonal (top-right to bottom-left)
// ...
// check the horizontal
// ...
// check the vertical
// ...
return false;

alternatively, if you don't like the nested loops (untested):

// check the primary diagonal (top-left to bottom-right)
int count = 0, maxCount = 0;
for (int x = left, y = top; x <= right && y <= bottom; x++, y++) {
    if (count < 5) {
        count = stones[x][y] == lastPlayer ? count + 1 : 0;
    } else {
        return true;
    }
}