Давно придумал кое-какое - вроде вполне хорошее решение, дополнительно можно и уровень игрока задать. Решение для крестиков-ноликов любого размера уровня, любой длины обычной или диагональной линии. Всё правильно должны быть только прямые линии?

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

И первый ход в ветке дерева с кратчайшим путем к выигрышу - это и есть оптимальный. Так?

Возникает вопрос, а как долго будет идти расчет и вообще реально ли это? Игральная доска 15 на 15 = 225! Это безмерное количество вариантов. Можно конечно глубину расчетов уменьшить, но мне интересно а есть ли альтернативные варианты вычислений?

А у тебя какого плана система вычислений?

Делал такой алгоритм сам - не было готового. Поле 15 на 15. Больше 13 ходов не выдерживал (проигрывал). Идея -  вычисление веса для свободной клетки на основании данных из соседних. 

Да, вообще тема большая. Самое примитивное решение - ставить в случайных местах главное чтоб по соседству к своим или к вражеским. Потом, решение типо шахматного - комбинирование своих-ответных на такую-то глубину, в данном случае будет наблюдаться около (200^2)^глубина. Чтоб игрок не уснул до следующего утра глубина = 2. Можно ускорить отбросив далёкие пустые клеточки, тогда допустим глубина = 5. Моё решение несколько неоднозначно пока. С его помощью можно отбрасывая бесполезные и маленькие вероятности рассматривать только примерно ходов (10^2)^глубина. Но оно работает вообще-то и без комбинирования - полностью без степенного роста возможных ходов с ростом глубины, глубина равна 1. Даже когда мы решаем задачу шахматным способом полезна примерная оценка по расположению выгодности хода, ввиду того что не хватит вычилительной мощности чтобы просмотреть даже приводящие к гарантированной победе ходы или абсолютно все ходы, где победы может не оказаться, но по крайней мере компьютер допустим не проиграет и сможет применить какой-нибудь упрощённый анализ выгодности хода, который всё равно не проигрышный - как лучше запутать игрока чтобы всё-таки выйграть. Моё решение довольно эффективно и представляет из себя вобщем где-то 5 решений:

0) придумано раньше и похуже - но оно даёт обзор подобного подхода - и подобный используется и в последующих 4;

1) больше чем 0 учитывает расположение соседних отметок;

2) дальнейшее развитие 1 - старается лучше оценить возможные последствия хода;

3) дальнейшее развитие 2;

4) дальнейшее развитие 3;

Я предпочитал рассматривать линии по 5, но решение для любого количества.

0) Предполагается что у нас есть думерный массив чисел на всё игровое поле - таблица. Обнуляем таблицу. Проходим все наши отметки и проводим все линии через отметку в нашем случае максимум 5 линий в четырёх направлениях то есть всего 20, не удастся провести линию если хоть одна клеточка линии занята врагом или если хоть одна клеточка линии выходит за пределы уровня - насчёт выхода за пределы, для оптимизации стоит сразу определить прямоугольник для всех линий пока они не выходят за границу и по размерам прямоугольника получать количество линий каждого направления. Если линия удалась ко всем позициям таблицы под линией без наших отметок добавляем 1 - но только в том случае если ещё не добавляли какой-нибудь предыдущей линией, значит нужно типо это дополнительно отмечать и сбрасывать только когда будем проходить уже следующую отметку или хотя бы направление линий. Подобным образом проходим и все вражеские отметки решая как бы за него - все добавления в одну и ту же таблицу. Остаётся случайный выбор из одинаковых максимальных значений в таблице - для 100% мастерства компьютера. Координата в таблице - положение на игровом поле.

1) Отличается от 0 тем что эта 1 добавляется без учёта того, была ли она добавлена какой-нибудь предыдущей линией.

2) Определяем некоторое число для определённой длины линии, в нашем случае 20 - максимум линий. Сделаем 2 таблицы вместо одной - для своих и для вражеских, а для того чтоб в остальном было как раньше будем их суммировать. Проходим значения в таблице что больше нуля, умножаем их на 20 в нашем случае и каждую такую кандидативную отметку меряем по количеству линий, которые могут там быть проведены по тем же принципам что и раньше. Прибавляем в таблицу это количество, отнимая единицу, так как значение было > 0 можно провести одну линию уже точно, значит прибавления будут от 0 до 19. Так же с вражескими - словно ходим за них.

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

4) Комбинируем с учётом вражеских в ответ.

Рекомендую остановиться где-то на 2 решении.

Возможно стоит учитывать одни и те же линии только один раз в зачёте удвадцатирённых.

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

Проигрывал за 14 ходов ты или компьютерный интеллект ?

Интересное решение, нужно подумать.

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

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

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

Вот https://sites.google.com/site/programmeraifromabog/clients/resources файл gomoku32.zip удивлюсь если вообще сможете выйграть. И таких непобедимых крестиков ноликов полно, имеет смысл сделать с меньшей сложностью.

У меня полчилось выиграть без проблем за 27 ходов. Скрин смотрите в почте.

Сначала удивился что вообще можно выйграть, но сам сейчас случайно как-то выйграл в 13 ходов. Что ж я думаю всем сайтом мы сможем таки извести игрока - разумеется с целью получить мастерскую игру компьютера чтобы потом можно было сделать разные сложности. Описанные решения по крайней мере после их доводки после испытаний наверняка превзойдут эту версию игры. Так что я ещё вполне уверен что решение удастся.

Про то я Вам и писал вначале, что если алгоритм продержится хотя бы  30 ходов то это можно считать очень сильным результатом.