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

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

Сродни игре когда из кучи камней двое берут попеременно по 1-3 камня, кто берет последний - выигрывает. Только вместо камней количество потенциальных полей для хода. Отличий 2:
1) в зависимости от позиции, каждый ход из всех возможных на доске отбирает у соперника от 0 до 3 ходов, но в каждой конкретной позиции на всей совокупности потенциальных ходов нижняя граница м.б. 0 или 1, а верхняя - от нижней до 1..3.
2) количество возможных ходов у соперников не обязано совпадать.

Посему вместо попытки построить алгоритм проще работать перебором с учетом указанных отличий. Имхо это несложно.

А можно поподробнее Akina ! Что именно перебирать и каким образом? И что должен дать этот перебер, т.е какой результат?Наиболее выгодный ход?Если да то по каким критериям?

Цитата(Exekutor @ 1.11.2005, 11:50)

Вообще для поиска беспроигрышной стратегии нужно использовать деревья.

Слово "нужно" нужно заменить на "можно"

Народ пли3, может хоть кто-нибудь сделает хоть какие-то наброски !?

И что? выложить код просто для обсуждения. Или подготовить уже к использованию.

Можно теорию графов притулить. (Те же деревья, только вкось...)

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