Написал игру в шашки, которая перебирает все комбинации на 3 хода вперед и выбирает лучшую. Если проводить анализ на 4-5 ходов вперед уходит непозволительно много времени. Надо видимо отбрасывать как-то сразу заведомо плохие ходы. Но как? Может быть кто-нибудь подскажет идею, как можно "обрубать ветки"? Заранее спасибо.

так как все таки у тебя реализовано на 3 хода или на 4-5?

Смотришь на 1 ход вперед. Отсеиваешь половину самых неблагоприятных.
У оставшихся смотриш на второй ход. ОТсеиваешь половину. и т.д. пока один не останется.

А как глядя всего на 1 ход вперед определить неблагоприятный этот ход или нет?

> [3] Jimmy   (26.08.08 23:36)

Так же как и для 3 ходов?

посмотрите готовый алгоритм, может разберетесь :)
http://www.rsdn.ru/Forum/Message.aspx?mid=241401&only=1
(С) Mystic

>!!ex
Через три хода я определяю "стоимость" позиции по количеству оставшихся шашек. Но это совсем не годится "через один ход".

если поле урезать по вертикали на 2, т.е сделать 8 на 6, количество шашек по 8 вместо 12-ти, то существует всего одна единственная выигрышная последовательность ходов.

Это можно как-то использовать?

Метод альфа-бета отсечений
Смысл -
до какого-то шага(3, допустим) исследуются все варианты.
Потом исследования более плохих на этом, 3м, на 4м шаге забрасываются.

Удалено модератором

Неплохо написано здесь: http://ocrai.narod.ru/chessalg.html
После применения хэш-таблиц и альфа-беты в моих шашках глубина увеличилась с 3 ходов (как и у Вас) до 5. А вообще, наверное имеет смысл и улучшать оценочную функцию, возможно, это более важно, чем увеличивать глубину.