Точнее мне нужен алгоритм ходов противника

Здравствуйте Styk, Вы писали:

S>Точнее мне нужен алгоритм ходов противника

Вот, что-то есть, если еще не поздно.

//--------------------------------------------------------------------------
1. Проверить для каждой шашки комп., может ли она что-то побить. Если да — то на п.6 , если нет — то на п.2
2. Ходить шашкой с максимальным удалением от начальной линии так, чтобы она не попала под бой (такие ходы не всегда есть)
3. Если ходов по п.2 нет — ходить шашкой с минимальным удалением от начальной линии (там моих шашек больше и больше вероятность простого обмена, а не жертвования моей шашки, под «моей» здесь и далее понимается шашка компьютера.)
4. Внести соответсвующие изменения в массив расположения шашек и вывести его на экран.
5. Конец хода. Передать ход человеку.
6. Побить. Правила шашек не допускают другого хода, если моя шашка может что-то бить. Внести соответсвующие изменения в массив расположения шашек и вывести его на экран.
7. Проверить, можно ли еще что-то побить той шашкой, которой мы только что били. Если можно — на п.6., если нельзя — на п.4.

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

Здравствуйте volk, спасибо за алгоритм.... есть с чего начать

Здравствуйте Styk, Вы писали:

S>Точнее мне нужен алгоритм ходов противника :-
Чтобы просчитать на K ходов вперед, используй перебор.
Для определенности пусть человек играет белыми, а комп. черными.

1. Выбрать любой из допустимых ходов черными.
2. Оценка = ЛучшийОтветБелых(1)
3 Повторить 1-2, например, 100 (или сколько там допустимых ходов) раз и выбрать лучший ход.

Как выбрать лучший ответ. В качестве параметра передается номер хода

ЛучшийОтветБелых(No хода)
{
  1. Выбрать любой из допустимых ходов белыми.
  2-а. Если (No хода<K) Оценка = ЛучшийОтветЧерных(No хода+1)
  2-б. Иначе Оценка = ФинальнаяОценкаБелых() - ФинальнаяОценкаЧерных()
  3. Повторить 1-2, например, 100 раз и выбрать лучший ход
  return лучшую оценку.
}

Лучший ответ черных пишется аналогично.

Как считаль финальную оценку (вариант).
За каждую шашку: 5 + расстояние от начальной линии — (5 если шашка заперта)
За дамку: 50 — 20 если дамка заперта + 10 если дамка на главной диагонали

Здравствуйте Styk, Вы писали:

S>Точнее мне нужен алгоритм ходов противника :-
Шашечный алгоритм делится на несколько частей:
1. Генератор ходов (самое сложное для начала
2. Оценка позиции.
3. Перебор.
4. (продвинутый) Всевозможные отсечения в переборе.

Перебор идет таким образом (самый простой вариант):
Генерируешь все возможные свои ходы; далее на каждый возможный ход генерируешь все варианты ответа, и так далее по рекурсии. В конце всего этого оцениваешь позицию (например шашка +100, дамка +250).

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

Здравствуйте Styk, Вы писали:

S>Точнее мне нужен алгоритм ходов противника

http://www.txm.ru/js2/index.html
См. раздел Игры

Вот, когда-то писал шашки...
http://mystic2000.newmail.ru/Draught.zip

Там был такой алгоритм

Есть буфер позиций, структура вроде стека. Далее

Рекурсивная функция оценки позиции

1. Буфер переполнен. Если да, то возвращаем оценку позиции по принципу у кого больше: простая 2, дамка 7.

2. Дописываем в буффер все возможные хода.

3. Если ходов нет, то возвращаем позиция проиграна (или выигрына, в зависимости от того, кто ходит)

4. Анализируем каждый ход по этой же процедуре.

5. Оценкой позиции будет ход с наименьшей (ходит противник) либо наибольшей (ходим мы) оценкой.

6. Очищаем буфрер.

Здравствуйте Styk, Вы писали:

S>Точнее мне нужен алгоритм ходов противника :-\

Три (или 4)года назад я занимался этим же, алгоритм поначалу строился как _экспертная система_ т.е. я в общем (независимо от координат фигуры) случае рассматривал все возможные ходы и давал им оценку, примерно по такому принципу:
— убьют: -1
— защита: +1
— выгодное положение: +1
— стать дамкой: +4
....
....
цифры задавались переменными константами, которыми я манипулируя задавал стиль игры: атакующий, пассивный, позиционный и т.д. Кроме того изменял их в процессе игры, если у противника меньше на одну фигуру (условно) увеличивал агрессию — тягу к разменам и т.д.
В результате этот "движок" (который я от скуки ежедневно расширял добавлением новых ситуаций) обыграл моего друга, когда тот был накурен... (20 лет). Когда год спустя я сел за него то начал думать в сторону целевой функции, не линейной, как раньше, а нелинейной с 32 входными параметрами(число черных клеток), если поговорить с математиком+экспертом в шашках, такую функцию можно подобрать, а с оптимизировать коэффициэнты дело статистики... Но я тогда все это переплюнул и стал копать под нейронные сети, построил многослойный перцептрон и обучал в процессе игры с соперником (если тот выигрывал принимал обучение), но перцептрон оказался слабоват и я придумал еще более крутую модель НС (взял у своего препода — тот защитился на распознавании образов, фоторобот короче) и с тех пор я не скучаю зимними долгими вечерами, у меня есть сильный противник...

Здравствуйте Styk, Вы писали:

S>Точнее мне нужен алгоритм ходов противника :-\

Боюсь, слишком долгого объяснения у меня не получится, но в хорошем алгоритме оценка и выбор ходов противника НИЧЕМ не отличается от оценки позиции ТОБОЙ на его месте. Другими словами, функция оценки обычно (но не всегда) симметрична. Не всегда — потому что иногда пишется игрок-attacker, иногда — defender. Как правильно было замечено sancoder, обычно для таких игр (с полной информацией) используются алгоритмы типа минимакс или, равноценный, но более быстрый (за счёт отсечения ходов) алгоритм альфа-бета. Конкретно про шашки могу подсказать ссылку на сайт нашего универа. В прошлом семестре, если мне не изменяем память, был турнир по шашкам среди программ. Есть довольно наивный алгоритм на ЛИСПе, НО так же есть турнирная таблица. Думаю, если попросишь (там есть e-mail), тебе пришлют адреса победителей. А там уже — общайся (англ. яз :) ).

Тебе сюда

Сорри, это был я.

Здравствуйте fAX, Вы писали:

Чуть не забыл: относительно наивный алгоритм игры тут. Также есть реализация альфа-беты и многого другого.

Удачи.