Алгоритм проверки соединения четырех полей

Мне интересно, что лучший способ проверить победителя на подключении четырех полей.

Меня интересует то, что вы, ребята, думаете и есть ли какой-то "известный" алгоритм для таких проблем?

Решение:

Я реализовал решение хеш-таблицы Ardavan в Python.

Я позволяю алгоритму работать над каждым полем один раз. Лучшее время проверки с моей реализацией было 0,047 мс, наихудшее 0,154 мс и среднее 0,114 мс на моем процессоре Intel (R) Core (TM) 2 Duo T9600 @2,80 ГГц. Это достаточно быстро для моих нужд, и алгоритм кажется мне опрятным.

Ответ 1

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

Ответ 2

Исходный код из Fhourstones Benchmark от John Tromp использует увлекательный алгоритм для тестирования соединения четырех игр для победы. Алгоритм использует следующее bitboard представление игры:

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42  BOTTOM

Существует одна битва для красного игрока и одна для желтого игрока. 0 представляет собой пустую ячейку, 1 представляет заполненную ячейку. Битовая часть хранится в неподписанной 64-битной целочисленной переменной. Биты 6, 13, 20, 27, 34, 41, >= 48 должны быть 0.

Алгоритм:

// return whether 'board' includes a win
bool haswon(unsigned __int64 board)
{
    unsigned __int64 y = board & (board >> 6);
    if (y & (y >> 2 * 6))     // check \ diagonal
        return true;
    y = board & (board >> 7);
    if (y & (y >> 2 * 7))     // check horizontal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8))     // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))         // check vertical
        return true;
    return false;
}

Вы должны вызвать функцию для бита проигрывателя, который сделал последний ход. Я пытаюсь объяснить алгоритм в своем ответе на вопрос "Как определить конец игры в tic-tac-toe?" .

Ответ 3

Это связано с этим вопросом: Как найти победителя тик-таковой игры любого размера?

Твист - это плата 7x6 с выигрышной победой 4, а не NxN-доска с N в выигрыше подряд. Но тривиально адаптировать решение к NxN tic tac toe для соединения 4.

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

Храните подсчет для каждого игрока за каждую строку, столбец, диагональ и диагональ, которые могут иметь 4 части подряд. Когда этот счет достигает 4 или более для любого игрока, проверьте, есть ли в этой строке/столбце/диагонали/антидиагонале четыре фигуры подряд. Если это так, побеждает этот игрок!