Обнаружение петель в компьютерном плеере в карточной игре

Question

Некоторое время назад я для развлечения создал небольшое веб-приложение для карточных игр.Плеер играет против компьютера и в основном работает нормально.Иногда, хотя компьютерный игрок зацикливается, смысл игры в том, чтобы потерять все свои карты, и если у вас нет карты для игры, вы берете колоду.Иногда компьютер играет x, y, z, берет кучу, играет x, yz, берет кучу и т.д.

Я отслеживаю шаги, которые я сделал, поэтому в любой момент у меня есть массив, которыйвыглядит примерно так: [C2, D5, H2, S4, C5, H2, S4, C5, H2, S4, C5 ]

В этом случае я вижу, что я получилв цикле игры H2, S4, C5, затем взятия стопки и повторения.

Итак, общая проблема в том, как лучше всего обнаружить повторяющиеся шаблоны в списке?Я мог бы, вероятно, набросать что-нибудь, используя простой цикл for, пытаясь найти карту, которую я собираюсь сыграть, и если я найду это в позиции x, то я смогу проверить, повторяется ли паттерн от x до n в позиции x- (nx)к х, но это похоже на проблему, которая может иметь хороший алгоритм для этого.Как бы вы закодировали это, учитывая следующую подпись функции:

function findLoops(previousMoves, nextMove, maxPatternLength) {
    //Return [loopLength, loopCount] or null if there are no loops
}

ps это не домашнее задание, игра существует и находится по адресу http://www.idiot -cardgame.com , если кто-либозаинтересован:)

Answer 1

Первый общий вопрос: Ваш предложенный метод

пытаясь найти карту, которую я собираюсь разыграть, и если я найду ее в позиции x, тогда я смогу проверить, повторяется ли комбинация от x до n в позиции x- (n-x) до x,

выглядит действительно хорошо. Я бы предложил в основном то же самое. Это O (n), он требует фиксированного объема памяти и прост: чего бы вы еще хотели?

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

В Javascript у вас есть встроенные hastables, так что это очень легко сделать с чем-то похожим на это:

 new_state = next_move(old_state);
 new_encoded_state = encode(new_state);  // make it into a string
 if (allstates[new_encoded_state]) {
       // we are looping!
 } else {
       allstates[new_encoded_state] = 1;
       // no looping
 }

Переменная allstates не является массивом, а имеет тип Object. Вы можете иметь массив, как доступ со строками, и это использует объект как hastable.