Победители на доске Пентаго

Question

Для тех, кто не знает, что такое Пентаго, это не очень важно для проблемы, но достаточно сказать, что у вас есть доска 6х6 с четырьмя квадрантами. Каждый игрок по очереди размещает фигуру, а затем вращает квадрант. Игра выигрывается, когда один игрок получает пять подряд (до или после фазы вращения игрока).

Я пишу алгоритм для игры во многие случайные игры Пентаго. Тем не менее, поскольку это абсолютно случайно, я не вижу хорошего способа обойти проверку того, выигрывает ли кто-то между местом и фазой поворота (в противном случае вы можете случайно повернуть выигрышный ход). В конце концов, я планирую переписать это так, чтобы в нем использовалось немного больше стратегии, чем полностью случайной, но это для статистических целей, так что случайность работает хорошо (и на самом деле весьма полезна в некоторых отношениях).

В любом случае, сейчас я программирую на Matlab, и пустая доска выглядит следующим образом

eeeeee
eeeeee
eeeeee
eeeeee
eeeeee
eeeeee

По ходу игры доска заполняется w и b. Способ, которым я проверяю выигрышную доску, заключается в буквальном переборе каждого столбца и каждой строки (и каждой диагонали), чтобы определить, есть ли победитель, выполнив проверку регулярного выражения для возвращаемой «строки».

Короче, мой вопрос таков:

Есть ли более эффективный метод определения победителей доски Пентаго?

Answer 1

РЕДАКТИРОВАТЬ:

Есть два решения, которые я придумал: одно на основе свертки (с использованием функции CONV2 ) и одно на основе грубойпринудительное индексирование для всех возможных строк из 5 элементов (аналогично более новому ответу b3 ).Вот они:

Свертка:

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

Индексация:

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

Из любопытства, подумал яЯ бы оценил скорость и точность этих решений по сравнению с более новым ответом b3 .Я создал 4 тестовых доски: -1 победа, без победителя, 1 победа, обе победы (ничья).Затем я запускал каждое решение 10000 раз для каждой доски и рассчитывал их время.Вот результаты:

               |   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

Обратите внимание, что решение b3 не может обнаружить ничью.Хотя код для решения на основе свертки был самым коротким и простым в реализации (мне не пришлось создавать список индексов вручную), решение по индексированию, которое я привел выше, в итоге оказывается самым быстрым.

Answer 2

Используйте числовой массив 6x6 для представления игрового поля, ноль для обозначения пустой позиции, 1 для обозначения черного и -1 для обозначения белого. Затем доска инициализируется:

>> 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

Чтобы проверить выигрышную доску, используйте SUM , которая работает со столбцами массива доски. Вычитание MIN столбца разрешит случай, когда столбец содержит фигуры от обоих игроков. Используйте аргумент измерения функций SUM и MIN, чтобы выполнить одинаковую проверку строк. Создайте массив из трех возможных диагоналей, используя DIAG , и заполните две более короткие диагонали нулями. Выполните ту же проверку для столбцов этого массива.

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

Теперь вы можете проверить доску, позвонив по номеру 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!

Answer 3

Используя предварительно вычисленные таблицы поиска, можно определить, есть ли у одного игрока пять подряд в 18 инструкциях.Следующая процедура принимает в качестве входных данных все камни одного игрока, упакованные в 64-битное целое:

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
}

Полный исходный код находится здесь:

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

Answer 4

РЕДАКТИРОВАТЬ: Обновлено с использованием новых алгоритмов Gnovices (всего 3 верно? Вы использовали filter (), теперь вы используете conv2 ()).

Новые числа:

                     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

Это было слишком весело, чтобы сопротивляться.Без B3 и кода Gnovice мой был бы пронизан ошибками.Насколько я могу судить, код Гновице, похоже, имеет 100% точность.B3 представил две функции: первая ложно присуждается победителю, если было 4 подряд, пробел и еще одна.Вторая запись B3 не может определить победителя по диагонали сверху справа внизу слева.B3 также не принял во внимание случай, когда оба игрока имеют выигрышные позиции.(Как я понимаю в игре, вращение квадранта может привести к тому, что оба игрока выиграют сразу?)

Вот список из 1000 случайных досок.

                     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 

Гновице был первымдостиг 100% точности, но пришел в самый высокий момент исполнения.B3, возможно, может изменить свой код, чтобы исправить ошибки, а затем получить самый быстрый код.И я, вероятно, мог бы получить жизнь вместо гонок, соединяя 4 кода друг с другом.

Вот мой код:

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

Вот код драйвера

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

К вашему сведению B3 - это пример платы, которую ваш код не смог обнаружить.

 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

а также

 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

Answer 5

В этом решении используется метод грубой силы, чтобы сравнить доску с возможными условиями выигрыша:

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