Winners on a Pentago board

Question

For those who don't know what Pentago is, it's not really that important to the problem, but suffice to say that you have a 6x6 board with four quadrants. Each player takes turns placing a piece and then rotating a quadrant. The game is won when one player gets five in a row (either before or after the player's rotate phase).

I'm writing an algorithm to play many different random Pentago games. However, since it's completely random, I see no good way to get around checking to see if someone wins in between the place and rotate phase of the turn (otherwise, you might accidentally rotate the winning move). Eventually, I plan on rewriting this to where it has a little bit more strategy involved instead of completely random, but this is for statistical purposes, so randomness does just fine (and in fact is quite useful in some ways).

Anyways, currently I am programming in Matlab, and an empty board looks like this

eeeeee
eeeeee
eeeeee
eeeeee
eeeeee
eeeeee

As the game progresses, the board fills with w's and b's. The way that I check for a winning board is quite literally iterating through every column and every row (and every diagonal) to see if there is a winner by performing a regular expression check on the "string" that is returned.

In short, my question is this:

Is there a more efficient method for determining the winners of a Pentago board?

Answer 1

EDIT:

There are two solutions I've come up with: one based on convolution (using the function CONV2) and one based on brute-force indexing for all possible strings of 5 elements (similar to b3's newer answer). Here they are:

Convolution:

function winner = pentago_winner_conv(board)
%# Input should be a 6-by-6 matrix with:
%#   - 0 for an empty space
%#   - 1 for pieces from one player
%#   - -1 for pieces from the other player
%# The return value is 0 for no winner, -1 or 1 for the winning player,
%#   or 2 if there is a draw.

  metric = [conv2(board,ones(1,5),'same') ...     %# Check horizontal strings
            conv2(board,ones(5,1),'same') ...     %# Check vertical strings
            conv2(board,eye(5),'same') ...        %# Check diagonal strings
            conv2(board,fliplr(eye(5)),'same')];  %# Check anti-diagonal strings
  limits = [min(metric(:)) max(metric(:))];  %# Find the min and max values
  limits = fix(limits/5);                    %# Convert them to -1, 0, or 1
  if all(limits)
    winner = 2;            %# A draw condition
  else
    winner = sum(limits);  %# Find the winner, if any
  end

end

Indexing:

function winner = pentago_winner_brute(board)
%# Input should be a 6-by-6 matrix with:
%#   - 0 for an empty space
%#   - 1 for pieces from one player
%#   - -1 for pieces from the other player
%# The return value is 0 for no winner, -1 or 1 for the winning player,
%#   or 2 if there is a draw.

  index = reshape(1:36,6,6);
  index = [index(1:5,:).'; index(2:6,:).'; ...  %# Vertical string indices
           index(:,1:5); index(:,2:6); ...      %# Horizontal string indices
           1:7:29; 2:7:30; 7:7:35; 8:7:36; ...  %# Diagonal string indices
           5:5:25; 6:5:26; 11:5:31; 12:5:32];   %# Anti-diagonal string indices
  metric = sum(board(index),2);
  limits = [min(metric) max(metric)];  %# Find the min and max values
  limits = fix(limits/5);              %# Convert them to -1, 0, or 1
  if all(limits)
    winner = 2;            %# A draw condition
  else
    winner = sum(limits);  %# Find the winner, if any
  end

end

Out of curiosity, I thought I'd measure the speed and accuracy of these solutions versus b3's newer answer. I created 4 test boards: -1 wins, no winner, 1 wins, both win (draw). Then I ran each solution 10,000 times for each board and timed them. Here are the results:

               |   Calculated winner
---------------+-----------------------
convolution    |  -1     0     1     2
indexing       |  -1     0     1     2
b3 solution    |  -1     0     1    -1

               |   Running time for 10,000x (seconds)
---------------+---------------------------------------
convolution    |  0.4863    0.5305    0.5248    0.4787
indexing       |  0.1706    0.1770    0.1755    0.1889
b3 solution    |  0.6607    1.3958    1.4223    0.7507

Note that b3's solution fails to detect a draw. Even though the code for the convolution-based solution was the shortest and easiest to implement (I didn't have to create a list of indices by hand), the indexing solution I give above ends up being the fastest.

Answer 2

Use a 6x6 numeric array to represent the game board, zero to indicate an empty position, 1 to indicate black and -1 to indicate white. A board is then initialized by:

>> board = zeros(6, 6)

board =

     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0

To check for a winning board use SUM which operates on the board array columns. Subtracting the MIN of the column will resolve the case where the column contains pieces from both players. Use the dimension argument of the SUM and MIN functions to perform the same check on the rows. Create an array of the three candidate diagonals using DIAG and pad the two shorter diagonals with zeros. Perform the same check on the columns of this array.

function result = checkBoard(board)

result = 'No winner';
diagonals = [diag(board, 0) [diag(board, 1); 0] [diag(board, -1); 0]];
if any(sum(board) - min(board) == 5) ...
        || any(sum(board, 2) - min(board, [], 2) == 5) ...
        || any(sum(diagonals) - min(diagonals) == 5)
    result = 'Black wins!';
elseif any(sum(-board) - min(-board) == 5) ...
        || any(sum(-board, 2) - min(-board, [], 2) == 5) ...
        || any(sum(-diagonals) - min(-diagonals) == 5)
    result = 'White wins!';
end

You can now check the board with a call to checkBoard:

>> x = [-1 0 0 0 0 0; -1 0 0 0 0 0; -1 0 0 0 0 0; -1 0 0 0 0 0; -1 0 0 0 0 0; 0 0 0 0 0 0]

x =

    -1     0     0     0     0     0
    -1     0     0     0     0     0
    -1     0     0     0     0     0
    -1     0     0     0     0     0
    -1     0     0     0     0     0
     0     0     0     0     0     0

>> checkBoard(x)

ans =

White wins!

>> x = [-1 0 0 0 0 0; -1 0 0 0 0 0; -1 0 0 0 0 0; -1 0 0 0 0 0; -1 0 0 0 0 0; 1 0 0 0 0 0]

x =

    -1     0     0     0     0     0
    -1     0     0     0     0     0
    -1     0     0     0     0     0
    -1     0     0     0     0     0
    -1     0     0     0     0     0
     1     0     0     0     0     0

>> checkBoard(x)

ans =

White wins!

>> x = [1 1 1 1 1 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0]

x =

     1     1     1     1     1     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0

>> checkBoard(x)

ans =

Black wins!

>> x = [1 0 0 0 0 0; 0 1 0 0 0 0; 0 0 1 0 0 0; 0 0 0 1 0 0; 0 0 0 0 1 0; 0 0 0 0 0 0]

x =

     1     0     0     0     0     0
     0     1     0     0     0     0
     0     0     1     0     0     0
     0     0     0     1     0     0
     0     0     0     0     1     0
     0     0     0     0     0     0

>> checkBoard(x)

ans =

Black wins!