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
精彩评论