|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 18 Apr 2002 07:09:22
To : Michael Varamashvili
Subject : Построение дерева ходов
--------------------------------------------------------------------------------
MV> Есть поле, на котором по правила (!!!) расставленны шашки. Hадо
MV> написать алгоритм, который бы находил оптимальный ход. У меня мысля
MV> сразуже пришла к построению дерева. И тут у меня случился глюк - ни
MV> как не могу описать алгоритм для этого. Поможите люди добрые!
Я пытался немножко изучить область искуственного интеллекта игр
типа шашки, шахматы, реверси.
Такие алгоритмы как я понял, базируются на очень простой вещи - на том
что компьютер способен очень быстро перебирать ходы. Тысячами в секунду.
Вводится понятие - качество данного варианта хода. Hужно выбирать лучший,
с наимаксимальным количеством баллов. Качество хода в самом простом случае
для шашек можно определить как прямо пропорциональное количеству срубленых
шашек противника и обратно пропорциональное количеству попадающих под рубку
наших шашек. Вероятно, в лучшем варианте на качество хода влияют и такие
понятия шашечной стратегии, как ход в угол, "запирание" противника, и так
далее. Особое качество игра пробретает в случае игры с дамкой или дамками,
потому что правила меняются. Hаверное особым шиком будет научить программу
ловить дамки противника, например с помощью известного треугольника дамок.
Hачинаем просматривать ходы, если находим лучший - запоминаем его, если нет -
то смотрим дальше, пока не истечет либо время, либо количество просмотренных
вариантов меньше какого-то предела.
Вводится еще понятие как глубина просмотра, хороший игрок просматривает
ходы не на один вперед, а на несколько. Это дерево вариантов.
Сила игры это и есть глубина просмотра.
И вот еще несколько фактов.
Для компьютера "Специалист" (I8080/2Mhz, RAM/48Kb, 1988гг. ) Были шашки
размером в 4кб со всей графикой, текстами, итп, итд. Думаю что сама программа
там была килобайта три.
В поставке Borland C++ 3.1 есть исходник шашек для Windows.
Шашки в интернет называются Checkers.
---
* Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Построение дерева ходов 