Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2004.09.05;
Скачать: CL | DM;

Вниз

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

 
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 :)


 
Ega23 ©   (2004-08-18 09:50) [9]

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

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


 
Юрий Зотов ©   (2004-08-18 12:20) [10]

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

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


 
Mim1 ©   (2004-08-18 13:07) [11]

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


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

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

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



Страницы: 1 вся ветка

Текущий архив: 2004.09.05;
Скачать: CL | DM;

Наверх




Память: 0.5 MB
Время: 0.049 c
6-1088507166
AVK
2004-06-29 15:06
2004.09.05
Проверка соединения, пинг.


4-1090317648
TRyaSS
2004-07-20 14:00
2004.09.05
COM-порт.Немогу записать в порт.


3-1092224632
snake1977
2004-08-11 15:43
2004.09.05
уникальный номер записи


1-1092999796
3APA3A
2004-08-20 15:03
2004.09.05
Корректное уничтожение форм, созданных в runtime...


11-1080221274
user
2004-03-25 16:27
2004.09.05
Как поднять скрол в верхнюю позицию не мышкой а програмно?