Какой алгоритм вы бы использовали для решения очень большой игры в крестики-нолики?

Question

Небольшой (3x3, 4x4) крестик-нолик можно легко решить, рассмотрев все случаи. Но, например, у вас есть крестики-нолики размером 30x30. Какой алгоритм вы бы использовали, чтобы решить следующий лучший ход в этом случае?

Минимакс + альфа-бета-обрезка - это один из известных мне способов.

Есть ли другой способ, который более эффективен / не более эффективен, но круче?

---

Я знаю, что играть в эту игру было бы не очень интересно. Я сказал 30x30, просто чтобы спросить, что я хотел, то есть какие алгоритмы работают лучше всего в играх такого типа, где число вариантов для идеального решения очень велико и, следовательно, неосуществимо.

Answer 1

Я не думаю, что это, вероятно, очень плодотворная проблема. Причина:

• Если количество очков в ряду, которое вам нужно выиграть, велико, игра (как мне кажется) будет нарисована с любым разумным уровнем мастерства, потому что намного легче предотвратить возможную победу, чем добейся этого сам. Например, если вам нужно 20 в ряд, чтобы выиграть на доске 30х30, все, что вам нужно для предотвращения победы, - это отметка на каждом ряду и столбце примерно в середине доски и отметка возле середины каждого столбца. длинная диагональ.

• Если количество очков в ряду, которое вам нужно выиграть, невелико, я подозреваю, что дополнительное место на игровом поле не будет иметь большого значения для стратегии и единственной разумной стратегии для Второй игрок для защиты будет играть рядом с вашим противником. В результате, какой-то альфа-бета метод подходит.

Answer 2

Для игры в Го, которая сложна для компьютеров по тем же причинам, которые беспокоят вас за 30x30 крестики-нолики (обратите внимание, что я не говорю, что 30x30 крестики-нолики это столь же сложный, как Go, и что более прямые методы неприменимы), поиск по дереву Монте-Карло недавно дал хорошие результаты.

Answer 3

Взгляните на Гомоку или Пять подряд. В Интернете существует ряд общих стратегий. В статье в Википедии также есть хорошая статья о поиске на основе угроз с гомоку, которую вы можете посмотреть.

Answer 4

Вы можете использовать Система на основе правил

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

Answer 5

Альфа-бета абсолютно лучшая вещь, которую вы можете использовать. Важность в альфа-бета заключается в его функции оценки. Который не возвращает только 1/0 / -1 (победа / ничто / проигрыш) (с одной точки зрения игрока), но также и квалификацию позиции.

Проверьте эту статью (в качестве примера он использует крестики-нолики, но в основном шахматы) http://www.fierz.ch/strategy1.htm

Answer 6

Разве не было бы хорошо использовать жадный алгоритм, который ищет соседнее пространство последнего хода и пытается поместить блок в любое пустое пространство, находящееся рядом со смежным элементом противника? Пока игрок не может выиграть, вы как бы выигрываете.

Answer 7

Поместите первый жетон в строку 3, столбец 3. Если противник поместит свой жетон в ряд 3, поместите следующий жетон в ряд 2, столбец 3, в противном случае в ряд 3, столбец 2. Вы должны быть в состоянии выяснить следующий (выигрышный) ход.

Если противник начинает, выберите пустой блок 4х4 и начните с середины, как описано выше. Если противник заканчивает свою тройку до вас, вы проигрываете.

Я бы осмелился сказать, что это оптимальная стратегия для досок 4х4 и выше.