Минимаксный метод...

← →
BoxTer (2004-08-18 07:40) [0]

Доброе время суток...
Наклюнулась интересная задачка. Предлагаю решить всем миром...
Итак, задача: - игра в даты.
Человек играет с железякой. Например, ходит человек, называет любое число и месяц, след. ход противник может назвать дату, в которой увеличен либо день (на любое значение), либо месяц (тоже на любое значение) - но в пределах ДО конца года... И так, пока кто-то(он и станет победителем) не скажет "последнее слово". Пример:
(1) - 5 января
(2) - 5 марта
(3) - 18 марта
(4) - 18 июля
......
(n-1) 30 декабря
(n) 31 декабря

Есть "граничное" значение: тот, кто сказал 20 января при умной игре всегда выиграет.
И самое интересное - решить нада все минимаксным методом...

← →
Думкин © (2004-08-18 07:49) [1]

А в чем задача?

← →
Mim1 © (2004-08-18 08:04) [2]

Бред какойто. :)

← →
BoxTer (2004-08-18 08:10) [3]

Бред, но нада сделать программулину "Игра" минимаксным методом. Была еще одна, ее сделали, там еще больший бред был :-)

← →
pavel_pavel © (2004-08-18 08:12) [4]

Задача прикольная кстати. Похожа на игру "ним" (в книжке какой-то давно прочитал): есть матрица (NxN) или (NxM) - не помню. Можно за 1 ход (игают тоже чел и комп) заполнить любую строку любым количеством клеток (матрица: boolean) проиграет тот, кто заполнит матрицу.

← →
Юрий Зотов © (2004-08-18 09:07) [5]

Есть N спичек. Двое берут их по очереди, причем за один ход можно взять не менее 1 и не более M спичек. Проигрывает тот, кто берет последнюю спичку.

Строим выигрышный алгоритм "от конца". Чтобы гарантированно заставить соперника взять последнюю спичку, перед нашим последним ходом в куче должно остаться ровно M+1 спичка. Значит, перед нашим предпоследним ходом в куче должно быть ровно <сообразите сами> спичек. И т.д. В результате получаем, сколько спичек нужно взять на нашем первом ходу, а затем на каждом следующем ходу берем столько спичек, чтобы дополнить взятое соперником число до M+1.

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

Вы спросите, при чем тут спички? А вот при чем.

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

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

← →
BoxTer (2004-08-18 09:37) [6]

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

← →
VMcL © (2004-08-18 09:46) [7]

>>BoxTer (18.08.04 07:40)

Ж. Арсак "Программирование игр и головоломок"

← →
VMcL © (2004-08-18 09:48) [8]

>>Юрий Зотов © (18.08.04 09:07) [5]

>Есть год, состоящий из 366 дней

Эта... 366 в високосном, в невисокосном 365 :)

Бред, но нада сделать программулину "Игра" минимаксным методом.

Господин студент, такие вещи делаются всем миром ЗА ДЕНЬГИ.

> VMcL © (18.08.04 09:48) [8]

Эта... по правилам игры (см. сабж) номер года не оговаривается, и, значит, 29 февраля можно назвать всегда. Таким образом, в игре фактически рассматриваются только високосные года.
:о)

Между тем DOOM III уже вышел :)

← →
BoxTer (2004-08-19 06:32) [12]

2Ega23: я уже 3 года как не студент. По образованию программер. Я просто люблю возиться с такими интересными задачками, причем бесплатно и для своего удовольствия... Моно сказать специально их ищу и бьюсь...

2ВсемОстальным: Спасибо, кто почесался. Сделал, вчерась после обеда... Получилось очень забавно - у компа практически невозможно выиграть :-) Крестики-нолики на поле n*m и то проще сделать...

Минимаксный метод... Найти похожие ветки