Winners on a Pentago board

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?

---

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.

---

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!

---

Using precomputed lookup tables, it's possible to detect whether one player has five in a row in about 18 instructions. The following routine takes as input all stones of one player packed into a 64-bit int:

inline quadrant_t quadrant(uint64_t state, int q) {
  assert(0<=q && q<4);
  return (state>>16*q)&0xffff;
}

// Determine if one side has 5 in a row
inline bool won(side_t side) {
  /* To test whether a position is a win for a given player, we note that
   * there are 3*4*2+4+4 = 32 different ways of getting 5 in a row on the
   * board. Thus, a 64-bit int can store a 2 bit field for each possible
   * method. We then precompute a lookup table mapping each quadrant state
   * to the number of win-possibilities it contributes to. 28 of the ways
   * of winning occur between two boards, and 4 occur between 4, so a sum
   * and a few bit twiddling checks are sufficient to test whether 5 in a
   * row exists. See helper for the precomputation code. */
  uint64_t c = win_contributions[0][quadrant(side,0)]
             + win_contributions[1][quadrant(side,1)]
             + win_contributions[2][quadrant(side,2)]
             + win_contributions[3][quadrant(side,3)];
  return c&(c>>1)&0x55 // The first four ways of winning require contributions from three quadrants
      || c&(0xaaaaaaaaaaaaaaaa<<8); // The remaining 28 ways require contributions from only two
}

The full source code is here:

https://github.com/girving/pentago/blob/9c9dedbb8dd3a5cf8dd778d28f351419126bbb7c/engine.cpp#L94

---

EDIT: Updated using Gnovices new algorithms (for a total of 3 right? you were using filter() now you are using conv2()).

New Numbers:

                     Apus     B3    B3   Gnovice 
                             Old   New   Orig  Conv Index
Player One Wins:        97   197    91    97    97    97 
Player Two Wins:       102   181   114   102   118   118 
Both Players Win:       16     0     0    16     0     0 
Neither Player Win:    785   622   795   785   785   785 
Execution Time:      0.081 0.037 0.144 0.317 0.068 0.036

This was too fun to resist. Without B3 and Gnovice's code, mine would have been riddled with errors. Gnovice's code appears to have 100% accuracy, as far as I can tell. B3 submitted two functions, the first falsely awarded a winner if there were 4 in a row, a space, and one more. B3's second entry fails to detect a winner on the diagonal from top right to bottom left. B3 also didn't take into account the case in which both players have winning positions. (As I understand the game, a quadrant rotation could cause both players to win at once?)

Here is the lineup, for 1000 random boards.

                     Apus     B3    B3   Gnovice
Player One Wins:       106   207   104   106 
Player Two Wins:       103   180   105   103 
Both Players Win:        6     0     0     6 
Neither Player Win:    785   613   791   785 
Execution Time:      0.082 0.037 0.146 0.322 

Gnovice was the first to hit 100% accuracy, but came in at the highest execution time. B3 could probably modify his code to fix the errors and then have the fastest code. And I could probably go get a life instead of racing connect 4 code against each other.

Here is my code:

function winner = testboard_apus(board)
answersheet1 = true(6,6);
answersheet1(6,:) = false(1,6);
answersheet2 = true(6,6);
answersheet2(1,:) = false(1,6);
winner = 0;
for player = 1:2
    if      any(sum((board==player) & answersheet1)==5)  ||...
            any(sum((board==player) & answersheet2)==5)  ||...
            any(sum((board'==player) & answersheet1)==5) ||...
            any(sum((board'==player) & answersheet2)==5) ||...
            all(diag(board(1:5,1:5))==player) ||...
            all(diag(board(2:6,2:6))==player) ||...
            all(diag(board(1:5,2:6))==player) ||...
            all(diag(board(2:6,1:5))==player) ||...
            all(diag(board(1:5,5:-1:1))==player) ||...
            all(diag(board(2:6,6:-1:2))==player) ||...
            all(diag(board(1:5,6:-1:2))==player) ||...
            all(diag(board(2:6,5:-1:1))==player)

        winner = winner + player;
    end
end
end

Here is the driver code

function testboard_wrapper

total = zeros(4,1);
agree = false(1000,1);
winner = zeros(1000,4);
for i = 1:1000
    board = floor(rand(6)*3);

    t(1) = tic;
    winner(i,1) = testboard_apus(board);
    total(1) = total(1)+toc(t(1));

    board2 = board;
    board2(board2==2) = -1;

    t(2) = tic;
    winner(i,2) = testboard_b3(board2);
    total(2) = total(2)+toc(t(2));

    t(3) = tic;
    winner(i,3) = testboard_b3_2nd(board2);
    total(3) = total(3)+toc(t(3));

    t(4) = tic;
    winner(i,4) = testboard_gnovice(board2);
    total(4) = total(4)+toc(t(4));

    agree(i) = all(winner(i,:)==0) || all(winner(i,:)==1) || all(winner(i,:)==2) ||all(winner(i,:)==3);

end

fprintf('                     Apus     B3    B3   Gnovice\n')
fprintf('Player One Wins:     %5i %5i %5i %5i \n',sum(winner==1))
fprintf('Player Two Wins:     %5i %5i %5i %5i \n',sum(winner==2))
fprintf('Both Players Win:    %5i %5i %5i %5i \n',sum(winner==3))
fprintf('Neither Player Win:  %5i %5i %5i %5i \n',sum(winner==0))
fprintf('Execution Time:      %1.3f %1.3f %1.3f %1.3f \n',total)
end

FYI B3 here is an example board your code failed to detect.

 0     0     0     0     0     2
 1     0     1     0     2     0
 1     2     1     2     1     0
 1     1     2     2     1     0
 0     2     2     0     0     2
 1     1     0     0     1     1

As well as

 0     2     2     2     0     2
 1     2     1     2     1     1
 0     0     2     0     0     2
 2     0     1     2     0     0
 2     0     1     0     2     0
 1     0     1     1     1     2

---

This solution uses a brute-force-esque approach to compare the board against the possible winning conditions:

function winner = pentago_winner(board)

if connectFive(-1)
    winner = -1;
elseif connectFive(1)
    winner = 1;
else
    winner = 0;
end

    function result = connectFive(player)
        result = find([all(~(board(1:5,:) - ones(5,6) * player)) ...                            % Check top 5 rows
            all(~(board(2:6,:) - ones(5,6) * player)) ...                                       % Check bottom 5 rows
            all(~(board(:,1:5)' - ones(5,6) * player)) ...                                      % Check left 5 columns
            all(~(board(:,2:6)' - ones(5,6) * player)) ...                                      % Check right 5 columns
            all(~([diag(board, 1) diag(board, -1)] - ones(5, 2) * player)) ...                  % Check minor diagonals
            all(~([diag(fliplr(board), 1) diag(fliplr(board), -1)] - ones(5, 2) * player)) ...  % Check minor anti-diagonals
            all(~(board(1:7:29)' - ones(5, 1) * player)) ...                                    % Check first 5 elements of major diagonal
            all(~(board(6:5:29)' - ones(5, 1) * player)) ...                                    % Check last 5 elements of major diagonal
            all(~(board(5:5:25)' - ones(5, 1) * player)) ...                                    % Check first 5 elements of major anti-diagonal
            all(~(board(12:5:32)' - ones(5, 1) * player))], 1) * player;                        % Check last 5 elements of major anti-diagonal
    end

end