|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Prosin 2:5025/911.14 10 Jun 2002 23:13:01
To : Mityay
Subject : просмотр вглубину
--------------------------------------------------------------------------------
Мои бортовые системы запеленговали, что в Суббота Июнь 08 2002 20:47, Mityay
писал All:
M> Интересует алгоритм просмотра в глубину в тех же шахматах, шашках.
M> Для простоты сойдут и крестики-нолики.
M> ...
Hе знаю насчет шахмат и шашек, но с более простыми играми можно поступать
так(или в тех же шахматах, но когда всего 2-3 фигуры осталось):
Hужно вести поиск не сначала(т.е. от исходной позиции), а с конца(т.е. с
позиций, где игра заканчивается).
Hапример, можно отметить 1 выигрышные положения и каким-то заведомо недостижимым
числом(т.е. числом ходов, которое не будет достигнуто) - проигрышные положения.
затем поступаем следю образом:
1)если из данной позиции можно получить только(!) выигрышную(т.е. 1), то позиция
проигрышная(отмечаем тем же большим числом).
2)если из данной позиции можно получить проигрышную, то позиция выигрышная, и
помечаем ее числом 1.
3)алгоритм завершаем, когда после нового прохода всех позиций не одна позиция не
была помечена.
В результате получим 1 во всех выигрышных позициях, большое число - в
проигрышных и начальные значения - во всех остальных(например, 0).
Если немного подумать, можно при этом учесть и последовательность ходов,
приводящих к победе (или к поражению). Отсюда и заведомо большое число в
проигрышных позициях, а не ,например, 2.
Может, конечно, это вряд ли тебе поможет в применении к алгоритму игры в шахматы
и шашки, однако для оценки эндшпиля подойдет.
Желаю удачи.
C уважением, Sergey Prosin.
--- УТВЕРЖДАЮ. MSG-редактор капитан 2.5 ранга Голд Дедович фор ДОС UNREG
* Origin: "Радость путешествия-посещение новых городов"Чин.Хан (2:5025/911.14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
просмотр вглубину