Помощь - Поиск - Пользователи - Календарь
Полная версия: Беспроигрышная стратегия
Форум «Всё о Паскале» > Pascal, Object Pascal > Написание игр
-FausT-
Народ, помогите пожалуйста чем можете, вот уже 2 месяца ломаю голову ,чтобы найти алгоритм беспроигрышной стратегии(ну естественно при каких-то условиях, скажем комп ходит первый(а стратегия нужна именно для компа) или человек).
Правила игры следующие:
Расположено подряд несколько кружков.Самый левый кружок закрашен красным цветом, а самый правый синим.Игроки, ходя по очереди,закрашивают красным или синим цветом выбранный ими ещё не закрашенный кружок. Игрок объявляется проигравшим, если после его хода окажется, что 2 соседних кружка закрашены разными цветами.
Требования: Один из игроков должен быть компьютер! И он должен играть по беспроигрышной(по возможности) стратегии!!!
Если есть какие мысли или кто-то может потратить своё драгоценное время и написать мне алгоритм буду очень признателен!!! Высказывайтесь!Просто ООООЧЕНЬ НУЖНО! Заранее благодарен откликнувшимся!
FreeMan
А можешь на листике нарисовать и отсканить партию, а то смутно себе это представляю?
-FausT-
К сожалению нет сканера и цифрового фотик в данный момент не имеется в наличии ,что конкоетно не понятно? условия проигрыша таковы:
Проигрывает тот кто поставит свою фишку так(фишку своего цвета) что слева или справа(т.е соседнии фишки) будет чужая фишка(т.е фишка другого цвета)!Количетсво кружков любое! Они стоят просто в линию, крайний правый синий, крайний левый красный!Каждый ходит фишкой своего цвета в любое свободное поле(но естественно не желательно, но можно, ходить в свободную но у котроой соседняя не твоя!(т.е это поигрыш, досрочный)) Теперь условия понятны?
Altair
Фауст ты не в МИЭМе учишься случайно ?
-FausT-
Олег ты что ли(K-32)? Как ты догадался? ;) Можешь тогда поможешь, у кого-то из ваших есть такая задача?
Altair
Фауст, посиди на форуме 2 года и будешь знать из каких инстов какие задачи приносят....
Цитата
Олег ты что ли(K-32)?

я...
Цитата
Можешь тогда поможешь, у кого-то из ваших есть такая задача?

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

зарегься что ли.. а то правила нарушаем... личная переписка выходит...
FausT2005
Вот зарегился, у кого-то говоришь есть? Хм... а ты не знаешь у кого точно? Этот человек хоть в состоянии что-нибудь сделать, не в курсе? blink.gif lol.gif

М
читай ПМ.
Altair

FausT2005
Ну что поможете? Олег, может ты чё подскажешь\ придумаешь могу кинуть наброски на QB !!
virt
напиши прогу которая для определенных введенных начальных условий перебором или еще как находит наилучшую стратегию игры ,сравни эти результаты и сделай вывод какой алгоритм.
Бродяжник
В принципе, можно сделать полный перебор дерева вариантов, благо по мере игры число возможных ходов сокращается. Кроме этого, на доске с нечетным количеством клеток всегда выигрывает первый игрок. В этом случае его стратегия такова: первый ход делается в середину доски, а все последующие - симметрично ходам соперника. На доске с четным количеством клеток для меня стратегия пока неочевидна, но наверное выгодно расставлять свои фишки так, чтобы между соседними было 1-2 пустых клетки, а вот ставить фишки впритык явно невыгодно. Более того, если на доске с четным количеством клеток первый игрок поставит свою первую фишку впритык к крайней, то доска станет доской с нечетным числом клеток, и тут уж должен выигрывать второй игрок. Доски с числом клеток меньше шести по-моему нет смысла рассматривать. Там все очевидно.
FausT2005
Спасибо за ответ, это я уже понял! Кстати первый ходя так как вы написали выигрывает всегда не только при нечетном количестве фишек, исключение 4 и 3 фишки, но это вариант смысла рассматривать нет(замечание: если количество фишек четное то ход делается не в середину а чуть правее!(т.е если фишек 8 ставим первым ходом в 5-ую начиная считать слева, если там ваша фишка)) Так вот, проблема для меня остаётся в том, как играть ходя вотрым, если противник не играет по этой выийгрышной стратегии...??! Помогите чем можете ,какие есть идеи при ходе вторым!
SKVOZNJAK
Идея есть но за наилучший алгоритм тебя повесят smile.gif)))) Потому как это на "проклятом операторе" строится cool.gif Алгоритм шашматный, размеры доски и количество фигур не имеют принципиального значения а имеет количество глобальных констант и переменных в компиляторе при большом количестве фигур. Каждый тип хода оценивается в баксах. Составляем список возможных ходов, суммируем заработанные каждой пешкой баксы на 1 ход, прибавляем баксы за второй и т. д. Промежуточные результаты не записываем, только рейтинг "баблоидности" фигуры, каждый раз персчитываем заново. Если у нескольких пешек одинаковый рейтинг, выбираем нужную случайным числом. В ходе теста отрегулируешь тарифную сетку платежей за ходы - бот не должен заниматься очковтирательством smile.gif
Lapp
Мне кажется, что есть стратегия выигрыша для первого игрока в любом случае, не только на нечетном поле. Фауст, если ты все еще заинтересован в решении - отзовись, попробую изложить. Ведь прошло уже немало времени, необходимость могла и пропасть..
Возможно, я и ошибаюсь в своих прикидках, но додумывать до конца буду только если это еще кому-то нужно. Начинает надоедать писать подробные посты, остающиеся без отклика, даже без спасиба, пусть и мелкими буковками.. sad.gif
FausT2005
Да, необходимости уже нет ,всем проявившим внимание и участие ОГРОМНОЕ СПАСИБО! good.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.