алгоритм для крестиков-ноликов

[denrubun]

надумал писать крестики нолики (5 в ряд)
и задался вопросом о том как будет соображать компьютер:
пока из мыслей приоритетность клеток + (отдельно) поиск троек - четверок, поставленных в ряд.
собственно интересует мнение форумчан, не надо тыкать в гугл.

[Виталий Желтяков]

Правильно думаете - поиск троек и чётвёрок в ряд + вилок. Если честно то достаточно просто для такой игры сделать матрицу ходов.

[denrubun]

матрицу ходов

можно капельку разъяснений?

вилки планирую искать так:
есть лист с тройками - четверками в ряд
я его просматриваю и нахожу клетки, которые могут "обломать" завершение их до пятерок
клетка, обламывающая сразу несколько комбинаций - она и предотвратит вилку

[phomm]

Начните с хотсит-игры, реализуйте всю логику - расстановки, очерёдности ходов, выигрыш-проигрыш. Сделайте графическое оформление простейшее.
А там видно будет - если грамотно сделаете, то подключить вместо одного хотсит-игрока модуль для оценки ходов - будет просто, сперва можно написать заглушку, которая принимает поле и ходит в рандомную клетку. Потом уже будем обсуждать предметно. В общем виде можно просто перебором с оценочной функцией сделать. Ссылки на подобные обсуждения с реализацией на оценочных функциях:
http://programmersforum.ru/showthread.php?t=33566
а также откройте поиск для себя - много тем на форуме, искать по ключевым словам "крестики нолики".

[denrubun]

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

[denrubun]

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

[Smitt&Wesson]

Сообщение от Виталий Желтяков

Правильно думаете - поиск троек и чётвёрок в ряд + вилок. Если честно то достаточно просто для такой игры сделать матрицу ходов.

Виталий, а Вы садист. Матрица игры, в комбинаторике, вычисляется как факториал. Например для матрицы 3Х3 число комбинаций буде (3 * 3)! = 362880. Для матрицы 5Х5=25! Мне даже представить страшно какая будет матрица.

[Виталий Желтяков]

можно капельку разъяснений?

Виталий, а Вы садист. Матрица игры, в комбинаторике, вычисляется как факториал. Например для матрицы 3Х3 число комбинаций буде (3 * 3)! = 362880. Для матрицы 5Х5=25! Мне даже представить страшно какая будет матрица.

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

[denrubun]

Я имел в виду матрицу выйгрышных комбинаций, а не полную матрицу ходов.
Достаточно просто проверять противника на эти комбинации и всё.

т.е. после хода противника мы проверяем не собрал ли он такую комбинацию и, если собрал, обламываем его, правильно понял? ну и сами тоже пытаемся такие создать.