45337

Понятие дерева возможностей

Доклад

Информатика, кибернетика и программирование

Дерево быстро разрастается рис.1 Дерево возможных продолжений шахматной игры Все вершины могут быть двух типов. Таким образом дерево возможностей представляет собой чередующиеся слои альфа и бетавершин. Если бы дерево можно было обследовать полностью т.

Русский

2013-11-16

36.5 KB

14 чел.

25 Понятие дерева возможностей

В программах-игроках наиболее полно удалось реализовать центральную идею искусственного интеллекта – обучение, самообучение и самоорганизацию компьютерных программ. Кроме того, понятие "игра" имеет более широкое значение. Игрой можно считать многие экономические, политические, военные и другие конфликты.

Проблемой создания игровых программ, в частности, шахматных, занимались многие ученые-кибернетики, такие как Тьюринг, Стречи, Шеннон, Нильсон. Принципы работы, предложенные каждым из разработчиков, опираются на исследования дерева возможных продолжений игры. Корневая вершина дерева возможностей представляет собой текущее положение фигур на шахматной доске, а работа программы состоит в выборе очередного хода.

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

Рисунок 7.1 – Дерево возможных продолжений шахматной игры

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

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


Комбинаторный взрыв

30

900

27 000

810 000


 

А также другие работы, которые могут Вас заинтересовать

70211. Техногенні та природні процеси порушення умов життя 155.5 KB
  Відповідно до причин походження подій що можуть зумовити виникнення надзвичайних ситуації на території України розрізняються: Таблиця 1 Класифікація надзвичайних ситуацій Надзвичайні ситуації Техногенного походження Природного походження Соціальнополітичного походження Воєнного походження...
70212. Kryminalistyka a jej wybrane elementy 723 KB
  Kształtowanie przedmiotu nauki kryminalistyki ma pewny historyczny aspekt, treść którego przed ten czas składa dyskusyjny problem. Przedmiot dowolnej nauki rozwija się, doskonalą się jego treść i metody w odpowiedniości do ogólnego gromadzenia naukowych wiedz i socjalnych warunków rozwoju społeczeństwa.
70214. Сущность, функции и основные задачи инвестиционного анализа 140 KB
  В общепринятом смысле инвестиции осознанный отказ от тек потребления в пользу возможного относительно большего дохода в будущем который как ожидается обеспечит и большее суммарное потребление. По определению инвестиции связаны с затратами и риском это главная особть...
70216. ХИМИЧЕСКАЯ СВЯЗЬ. СТРОЕНИЕ ВЕЩЕСТВА 305 KB
  В 1852 году английский исследователь Франкланд ввел понятие валентности (атомности). Валентность выражает способность атома данного элемента вступать в соединение с определенным числом атомов другого элемента. Приняв валентность водорода за единицу, можно считать, что валентность...
70217. ГЕНЕЗИС И ЭВОЛЮЦИЯ ФИНАНСОВ 71.5 KB
  Финансы как экономическая категория Общественно-экономические системы различаются экономическими отношениями которые в свою очередь являются производными от уровня и характера развития производительных сил. При этом финансы не могут не учитывать отношения распределения...
70218. УГОЛОВНО-ИСПОЛНИТЕЛЬНОЕ ПРАВО 217 KB
  Уголовно-исполнительная политика направление деятельности государства в его специально уполномоченных органах в сфере исполнения уголовного наказания. Уголовно-исполнительная политика определяет: цели; принципы; стратегию; основные направления формы методы деятельности...
70219. Фотокомпозиция 77.5 KB
  Композиция – построение, группировка и последовательность изобразительных приёмов, организующих идейно-художественное целое; соотношение и взаимное расположение частей. Точка съёмки – это положение фотоаппарата по отношению к снимаемому объекту. Ниже приведена классификация точки съемки.