|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrei Bejenari 2:5020/400 10 Jun 2002 15:41:56
To : Mityay
Subject : Re: просмотр вглубину
--------------------------------------------------------------------------------
"Mityay" <Mityay@p777.f119.n5011.z2.fidonet.org> wrote in message
news:1023548313@p777.f119.n5011.z2.ftn...
> Здpавия желаю, *All*!
>
> Интересует алгоритм просмотра в глубину в тех же шахматах, шашках. Для
> простоты сойдут и крестики-нолики. Делаться, я думаю, должно что-то вроде
> такого:
[skip]
> Вся проблема в том, что эта функция может давать неправильные ходы:
так,
> если следующим ходом противник может выиграть, а машина видит, что сама
может
> выиграть через 2 хода, если человек сыграет как полный идиот, то она
выбирет
> именно такой путь, дав, на самом деле, выиграть человеку на следующем
ходу.
Вот именно! Короче, в играх обычно просмотр дерева игры не в глубину
делается,
а в ширину. Выбор эвристической функции зависит от конкретной игры. Более
того
их может быть несколько, чтоб давать более точные оценки о ходах. Так же,
чтоб
не было таких казусов, как ты описал выше, анализируются по возможности все
ходы противника. В крестиках-ноликах (3х3) можно без проблем в память машины
поместить все дерево и игры и потом на нем просто пометить какие ходы ведут
к проигрышу, выигрышу или ничье. В шахматах, там все намного сложнее, все
дерево никак не поместится в память ни одного из существующих
супер-компьютеров.
Поэтому в начале игры обычно используется программирование типовых ситуаций,
т.е. он сразу знает какие позиции потом могут привести в выигрышу, а какие
ни к чему
хорошему не приведут. А далее уже строиться дерево игры, но опять же не все,
а только
на несколько ходов вперед, оцениваются листья дерева и выбераем ход.
Минимаксный
принцип используется.
> Значит, чем глубже смотрим - тем должны быть меньше коэффициенты, на
которые мы
> умножаем Ocenka? И какие-то сверх-коэффициенты для случаев, когда можно,
> условно говоря, поставить на следующем ходу "мат". Далее: как определить,
на
> какой ход человека машине рассчитывать? Те же шахматы всегда проводят
Вообще на любой ход надо расчитывать. Просто если видим, что этот ход
приводит к его же поражению, то просто продолжать строить дерево игры
после этой позиции не надо.
> определенную линию игры и видят HАИБОЛЕЕ ВЕРОЯТHЫЕ ходы человека. Как это
> реализовать?
Возможно, если сделать статистику, то какие-то ходы будут более вероятны
:)))
А так, а-приори, у всех ходов вполне одинаковые вероятности.
> Hаконец, стоит ли обходиться таким простым методом, как CountFigures
> (просто сосчитать число фигур на доске одного игрока и другого и вернуть
> разницу, можно отрицательную) или надо проводить дополнительный анализ?
Как это
> сделать?
Это тоже будет давать одну оценку. Только ей, конечно, ограничиваться не
стоит.
В шахматах, например, там же есть фигуры более важные и менее важные.
Поэтому
позиция в которой ты потеряешь пешку, хуже чем та в который ты потеряешь
ладью
(хотя конечно еще зависит от их расположения), вот имеем еще одну оценку, и
т.п.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: просмотр вглубину 