| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Минимаксный метод... [D5, Win2k]
BoxTer © (2004-08-18 07:40:00)Доброе время суток...
Наклюнулась интересная задачка. Предлагаю решить всем миром...
Итак, задача: - игра в даты.
Человек играет с железякой. Например, ходит человек, называет любое число и месяц, след. ход противник может назвать дату, в которой увеличен либо день (на любое значение), либо месяц (тоже на любое значение) - но в пределах ДО конца года... И так, пока кто-то(он и станет победителем) не скажет "последнее слово". Пример:
(1) - 5 января
(2) - 5 марта
(3) - 18 марта
(4) - 18 июля
......
(n-1) 30 декабря
(n) 31 декабря
Есть "граничное" значение: тот, кто сказал 20 января при умной игре всегда выиграет.
И самое интересное - решить нада все минимаксным методом...
BoxTer (2004-08-19 06:32:00) [1]2Ega23: я уже 3 года как не студент. По образованию программер. Я просто люблю возиться с такими интересными задачками, причем бесплатно и для своего удовольствия... Моно сказать специально их ищу и бьюсь...
2ВсемОстальным: Спасибо, кто почесался. Сделал, вчерась после обеда... Получилось очень забавно - у компа практически невозможно выиграть :-) Крестики-нолики на поле n*m и то проще сделать...
Mim1 (2004-08-18 13:07:00) [2]Между тем DOOM III уже вышел :)
Юрий Зотов (2004-08-18 12:20:00) [3]> VMcL © (18.08.04 09:48) [8]
Эта... по правилам игры (см. сабж) номер года не оговаривается, и, значит, 29 февраля можно назвать всегда. Таким образом, в игре фактически рассматриваются только високосные года.
:о)
Ega23 (2004-08-18 09:50:00) [4]Бред, но нада сделать программулину "Игра" минимаксным методом.
Господин студент, такие вещи делаются всем миром ЗА ДЕНЬГИ.
VMcL (2004-08-18 09:48:00) [5]>> Юрий Зотов © (18.08.04 09:07) [5]
> Есть год, состоящий из 366 дней
Эта... 366 в високосном, в невисокосном 365 :)
VMcL (2004-08-18 09:46:00) [6]>> BoxTer (18.08.04 07:40)
Ж. Арсак "Программирование игр и головоломок"
BoxTer (2004-08-18 09:37:00) [7]Интересно, а матрица весов подойдет для данной задачи? Т.е, грубо говоря, сделаю матрицу размером 31х12 - где в качестве значений ячейки бедет "вес", т.е. приоритет, чем выше вес, тем боле железка должна стремиться к нему. Стоим на какой-либо ячейке (текущий ход) - смотрим возможные, куда можем сходить, ищем среди них с максимальным весом и идем туда...
Юрий Зотов (2004-08-18 09:07:00) [8]Есть N спичек. Двое берут их по очереди, причем за один ход можно взять не менее 1 и не более M спичек. Проигрывает тот, кто берет последнюю спичку.
Строим выигрышный алгоритм "от конца". Чтобы гарантированно заставить соперника взять последнюю спичку, перед нашим последним ходом в куче должно остаться ровно M+1 спичка. Значит, перед нашим предпоследним ходом в куче должно быть ровно <сообразите сами> спичек. И т.д. В результате получаем, сколько спичек нужно взять на нашем первом ходу, а затем на каждом следующем ходу берем столько спичек, чтобы дополнить взятое соперником число до M+1.
У этой игры есть 2 состояния (определяются текущим количеством спичек). В одном состоянии гарантированно выигрывает первый ходящий, в другом - второй (при его правильной игре, конечно). Если игра находится в выигрышном для нас состоянии, то и так хорошо. А если в проигрышном, то при правильной игре соперника мы всегда проиграем, но если соперник ошибся, то тут же нужно взять столько спичек, чтобы привести игру в выигрышное состояние.
Вы спросите, при чем тут спички? А вот при чем.
Есть год, состоящий из 366 дней (то же самое, что куча из 366 спичек). Двое по определенным правилам называют даты (то есть, берут из кучи спички - причем количество взятых за раз спичек не превышает некоторого M, но это M динамически меняется по ходу игры). И т.д.
Получили ту же самую игру в спички, только в усложненом варианте. Выигрышный алгоритм строится так же, но применять его надо на каждом шаге (поскольку на каждом шаге меняется M).
pavel_pavel (2004-08-18 08:12:00) [9]Задача прикольная кстати. Похожа на игру "ним" (в книжке какой-то давно прочитал): есть матрица (NxN) или (NxM) - не помню. Можно за 1 ход (игают тоже чел и комп) заполнить любую строку любым количеством клеток (матрица: boolean) проиграет тот, кто заполнит матрицу.
BoxTer (2004-08-18 08:10:00) [10]Бред, но нада сделать программулину "Игра" минимаксным методом. Была еще одна, ее сделали, там еще больший бред был :-)
Mim1 (2004-08-18 08:04:00) [11]Бред какойто. :)
Думкин (2004-08-18 07:49:00) [12]А в чем задача?
| |
