Re: просмотр вглубину

From

Andrei Bejenari ()

To

Mityay

Date

2002-06-10T15:41:56Z

Area

RU.ALGORITHMS

From: "Andrei Bejenari" <andrei.bejenari@wanadoo.fr>

"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? И какие-то сверх-коэффициенты для случаев, когда можно,
> условно говоря, поставить на следующем ходу "мат". Далее: как определить,
на
> какой ход человека машине рассчитывать? Те же шахматы всегда проводят

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

> определенную линию игры и видят НАИБОЛЕЕ ВЕРОЯТНЫЕ ходы человека. Как это
> реализовать?

Возможно, если сделать статистику, то какие-то ходы будут более вероятны
:)))
А так, а-приори, у всех ходов вполне одинаковые вероятности.

>     Наконец, стоит ли обходиться таким простым методом, как CountFigures
> (просто сосчитать число фигур на доске одного игрока и другого и вернуть
> разницу, можно отрицательную) или надо проводить дополнительный анализ?
Как это
> сделать?

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


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)