Алгоритм для игры крестики-нолики #151180

Есть набор множеств А1={a11,a12,…} А2={a21,a22,…} ……………….. An={an1,an2,….} Где a11,… числа от 1 до K Найти множество минимальной мощности, в котором есть по крайней мере хотя бы один элемент из каждого из множеств A1…An.

Не осилил. По-моему, алгоритм игры в крестики-нолики куда проще.

Пример: A1={1,2,5} A2={2,3} A3={5} Решение B={2,5}

Что означают цифры?

цифры это натуральные числа из интервала от 1 до К. Вообщето К=225

Что ОЗНАЧАЮТ эти цифры?

скажем так... для чего они тогда...

С таким вопросом лучше будет сходить на форум - там такие вопросы любят и отвечают с удовольствием.

Алгоритм игры в крестики и нолики раз в 50 проще. 1с-ники головоломки тож любят ...

множество минимальной мощности - ЭТО ШО?

Это важно? Пусть это будет абстракная задача никак не связанная с игрой в крестики-нолики Спасибо за ссылко. Но мне хотельсь бы увидеть решение на платформк 7.7. Кстати разработать структуру хранения множеств А1,...Аn есть составная часть задачи. Мощность множества = количеству элементов множества

Решение на 1с практически ничем не будет отличаться ото всех других ...

Неоптимизированный алгоритм - хоть сейчас могу сказать ...

Можно устроить турнир программ по игре в крестики-нолики. У меня где-то завалялась программа для поля 3х3, написанная ещё на TP7. Думаю, несложно будет её переделать под 1С.

турнир уже объявлен

Для поля 3х3 можно заложить в базу все варианты - их не так уж и много, кажется, около 100.

Просто объявляешь "квадратный" массив. Далее юзаешь его. Кол-во столбцов и КОл-во строк - основные размерности. Далее находишь по алгоритмам эти множества ...

Ну, я точно не так делал. Вроде бы там одна-единственная беспроигрышная тактика.

Для 3х3 и закладывать нечего. Первый в угол, второй в центр и ничья

аха либо ничья... либо победа... смотря чей ход первый...

Я думаю, что начать можно и с 3х3, а потом уже переходить на более широкие масштабы. :)

какая разница чей первый, главное в угол

А вот это неважно, чей ход первый. Всегда можно сыграть вничью.

3Х3 уже потренировался. Хочу переходить на более широкие масштабы

Если алгоритмом в котором находяться комбинации - то нет. Надо сделать ИИ ...

А если в центр сходил противник?

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

ИИ тут и близко не стояло. Самое большее - полная рекусия на всю партию.

А я сказал "беспроигрышная" тактика. Выигрышной действительно нет.

Если поле очень большое, то рекурсия затянется. На 8.0 может даже вылететь (там глубина рекурсии ограничена).

Ну это, конечно, не самый оптимальный вариант (одна рекурсия).

ПРи чем тут рекурсия? Нельзя ли хоть чуть чуть логику ему прописать .. Она же там простая ....

Одно другому не мешает. Мы говорим про рекурсивный обход возможных ходов, а логику пропиши в оценочную функцию, как и делается во всех шахматных программах.

оценочная функция - это неправильно. Рекомендую: Р.Лингер и др. "Теория и практика структурного программирования" глава 7.6. Использование эвристического и строгого подходов: игра в крестики-нолики.

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

Могу дать ссылки на две программы (исходники)- в обеих используется Альфа-бета и оценочная функция.

если вас это не затруднит...

тут Это первые - исходники на сях.

Ссылка в предпоследнем посте. Для скачивания - возможно нужна регистрация. Текст на VB.

спасибо... скачал... на пенсии поковыряю ;))

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

сейчас просто ломает... я жду расчет..

Есть ли у кого идеи по поводу решения задачи в ?

Вообще то это задача о минимальном вершинном покрытии графа. Соответсвенно NP-полная - решается полным перебором. Может кто подскажет приблизительный алгоритм решения задачи

может туплю.... что такое "минимальной мощности"?..

отурытые тройки ищешь? Да, есть. Берем все множества из трех своих фишек на пять расположенных на одной линии клеток. Свободных клеток две. Например a1 0 0 а2 0 Делаем ТЗ с двумя колонками. ТЗ.НоваяСтрока; ТЗ.п1="а1"; ТЗ.п2="а2"; ТЗ.НоваяСтрока; ТЗ.п1="а2"; ТЗ.п2="а1"; Теперь необходимо учеть, что каждая комбинация из двух свободных клеток на пяти может встречаться несколько раз. (например 0 а1 0 0 а1 0) - первые пять, и последние пять. Чтоб это устранить - делаем ТЗ.Свернуть("п1,п2"); Теперь если после ТЗ.Свернуть("п1","") - количество строк уменьшилось, значит есть открытая тройка, то есть ход после которого есть возможность выиграть более, чем одним способом.

(+45) Для свободных клеток больше двух - просто добавляешь все комбинации - например для трех свободных- а1,а2,а3 - добавляешь все шесть перестановок, а потом так-же сворачиваешь по первой колонке. Если необходимо определить именно в каких поллях вилки - то Добавляем новую колонку, заполняем единицами (после сворачивания по всем колонкам) - сворачиваем по первой колонке, и где значение больше одного - там пересечение.

А вообще - очень быстрая оценка в программе в Хотя конечно так себе.

за алгоритмы спасибо. Но я решаю другую задачу. Есть множество угроз соперника (это не обязательно тройки, это скорее двойки), которые можно отразить своим ходом, а можно иподождать. Надо найти оптимальный порядок ходов отражающий все эти угрозы. Скажем есть N точек, где соперник МОЖЕТ своим ходом построить тройку (не обязательно тройку, главное что после хода соперника надо на нее реагировать немедленно). Список таких точек я построил. Для каждой точки определил способы отражения угрозы (это не обязательно текущяя точка, список может бфть довольно длинным). Отражать угрозу необязательно немедленно, но хочется своим ходом отразить максимальное количество угроз.

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

Кто тебе мешает не оперировать множествами, а посмотреть, что перекрывашь сопернику по обеим диагоналям, вертикали и горизонтали отдельно? На самом деле для оценки достаточно знать - что-бы постоил соперник данным ходом. Чтоб узнать это - надо взять девять (восемь точек), например четыре слева по горизонтали, и четыре справа. Вариантов комбинаций - 3^8<10000 (можно использовать массив, в который запишем изменения происходящее при постановки фишки в центр - например открытая двойка меняется на закрытую тройку, или открытая двойка переходит в открытую тройку) (три значения - за границе поля, или фишка не того, за кого берем оценку, фишка того, за кого берем оценку, и фишка соперника)

мощность множества = количество элементов множества

NS спасибо за советы. Воспользовался советом в переделал ТЗ для анализа ходов. стал анализировать не каждую свободную клетку поля, а каждую свободную линию. По 4 линии на каждую клетку. Алгоритм стал проще, быстрей и понятней. Совет из тоже оказался полезным. Программа стала очень шустрой меня и обработку с проклаба обыгрывает легко.

Доделываю менеджер, и сегодня прикручу блок к обработке на проклубе для игры с менеджером. Скоро сможешь с ней матч через менеджер устроить ;-)) Как раз, как только выложу - устроим перекличку, и определимся со списком участников.

Задача №2 Дан граф G=(V,E) где V множество вершин графа, E множество ребер графа. Множество ребер E разбито на два подмножества E1 и E2 (E=E1+E2). Найти путь от вершины «a» до вершины «b», причем путь должен начинаться и заканчиваться ребром из множества E1, затем ребра должны чередоваться. Путь P={x1,y2,…,yn-1,xn}, где x1,x2…xn принадлежат множеству E1,  y2,…yn-1 принадлежат E2.

Есть город со сложной схемой улиц и перекрестков. В нем множество тоннелей и эстакад, причем, так получилось, что на перекресток может выходить сразу много улиц аж до тринадцати. Мэр города с целью упорядочения движения раскрасил улицы в зеленый и оранжевый цвета. Водителям предписывается, если они подъехали к перекрестку по зеленой улице, то обязаны продолжить движение по оранжевой улице и наоборот. Развороты запрещены на всей территории города. Как проехать водителю из пункта А в пункт Б, и не нарушить правила.

По МКАДу.

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

Можно попробовать искать множества доступных улиц с обоих концов Т.е. из начальной точки выбрать доступные улицы для движения (мн1) из конечной точки выбрать доступные улицы для движения (мн2) --- выбрать доступные улицы для мн1 выбрать доступные улицы для мн2 --- Искать до тех пор, пока мн1 и мн2 не пересекутся или (мн1 или мн2 будуи содержать множество всех доступных улиц) --- Это при условии, что по улице можно проехать только один раз Можно искать из одной точки до тех пор пока не достигнем второй

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