Беспроигрышная стратегия, неужели такая хитрая... Опции

[-FausT-]

Народ, помогите пожалуйста чем можете, вот уже 2 месяца ломаю голову ,чтобы найти алгоритм беспроигрышной стратегии(ну естественно при каких-то условиях, скажем комп ходит первый(а стратегия нужна именно для компа) или человек).
Правила игры следующие:
Расположено подряд несколько кружков.Самый левый кружок закрашен красным цветом, а самый правый синим.Игроки, ходя по очереди,закрашивают красным или синим цветом выбранный ими ещё не закрашенный кружок. Игрок объявляется проигравшим, если после его хода окажется, что 2 соседних кружка закрашены разными цветами.
Требования: Один из игроков должен быть компьютер! И он должен играть по беспроигрышной(по возможности) стратегии!!!
Если есть какие мысли или кто-то может потратить своё драгоценное время и написать мне алгоритм буду очень признателен!!! Высказывайтесь!Просто ООООЧЕНЬ НУЖНО! Заранее благодарен откликнувшимся!

[FreeMan]

А можешь на листике нарисовать и отсканить партию, а то смутно себе это представляю?

[-FausT-]

К сожалению нет сканера и цифрового фотик в данный момент не имеется в наличии ,что конкоетно не понятно? условия проигрыша таковы:
Проигрывает тот кто поставит свою фишку так(фишку своего цвета) что слева или справа(т.е соседнии фишки) будет чужая фишка(т.е фишка другого цвета)!Количетсво кружков любое! Они стоят просто в линию, крайний правый синий, крайний левый красный!Каждый ходит фишкой своего цвета в любое свободное поле(но естественно не желательно, но можно, ходить в свободную но у котроой соседняя не твоя!(т.е это поигрыш, досрочный)) Теперь условия понятны?

[Altair]

Фауст ты не в МИЭМе учишься случайно ?

[-FausT-]

Олег ты что ли(K-32)? Как ты догадался? ;) Можешь тогда поможешь, у кого-то из ваших есть такая задача?

[Altair]

Фауст, посиди на форуме 2 года и будешь знать из каких инстов какие задачи приносят....

Олег ты что ли(K-32)?

я...

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

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

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

[FausT2005]

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

М

читай ПМ. Altair

[FausT2005]

Ну что поможете? Олег, может ты чё подскажешь\ придумаешь могу кинуть наброски на QB !!

[virt]

напиши прогу которая для определенных введенных начальных условий перебором или еще как находит наилучшую стратегию игры ,сравни эти результаты и сделай вывод какой алгоритм.

[Бродяжник]

В принципе, можно сделать полный перебор дерева вариантов, благо по мере игры число возможных ходов сокращается. Кроме этого, на доске с нечетным количеством клеток всегда выигрывает первый игрок. В этом случае его стратегия такова: первый ход делается в середину доски, а все последующие - симметрично ходам соперника. На доске с четным количеством клеток для меня стратегия пока неочевидна, но наверное выгодно расставлять свои фишки так, чтобы между соседними было 1-2 пустых клетки, а вот ставить фишки впритык явно невыгодно. Более того, если на доске с четным количеством клеток первый игрок поставит свою первую фишку впритык к крайней, то доска станет доской с нечетным числом клеток, и тут уж должен выигрывать второй игрок. Доски с числом клеток меньше шести по-моему нет смысла рассматривать. Там все очевидно.

[FausT2005]

Спасибо за ответ, это я уже понял! Кстати первый ходя так как вы написали выигрывает всегда не только при нечетном количестве фишек, исключение 4 и 3 фишки, но это вариант смысла рассматривать нет(замечание: если количество фишек четное то ход делается не в середину а чуть правее!(т.е если фишек 8 ставим первым ходом в 5-ую начиная считать слева, если там ваша фишка)) Так вот, проблема для меня остаётся в том, как играть ходя вотрым, если противник не играет по этой выийгрышной стратегии...??! Помогите чем можете ,какие есть идеи при ходе вторым!

Сообщение отредактировано: FausT2005 - 7.11.2005 22:16

[SKVOZNJAK]

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

[Lapp]

Мне кажется, что есть стратегия выигрыша для первого игрока в любом случае, не только на нечетном поле. Фауст, если ты все еще заинтересован в решении - отзовись, попробую изложить. Ведь прошло уже немало времени, необходимость могла и пропасть..
Возможно, я и ошибаюсь в своих прикидках, но додумывать до конца буду только если это еще кому-то нужно. Начинает надоедать писать подробные посты, остающиеся без отклика, даже без спасиба, пусть и мелкими буковками..

Сообщение отредактировано: lapp - 8.12.2005 10:07

[FausT2005]

Да, необходимости уже нет ,всем проявившим внимание и участие ОГРОМНОЕ СПАСИБО!