45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

14 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

38672. ПРАВОСЛАВНЫЕ ХРАМЫ СИМФЕРОПОЛЯ (КОНЕЦ XVIII – НАЧАЛО XXI ВЕКА) 330 KB
  Изучение вопросов религии, и её места в жизни общества представляет насущную задачу в наше время. Долгое время проблемы религии не рассматривались, так как шли вразрез с советской идеологией. Доступ к данным по возникновению и развитию православных храмов был ограничен, что обусловило отсутствие информации во многих исследованиях и учебных пособиях по истории
38673. Монтаж ленточных фундаментов и гидроизоляцию фундаментов одноэтажного здания с размерами в плане 61,8×30м 399 KB
  1 Технологическая карта разработана на монтаж ленточных фундаментов и гидроизоляцию фундаментов одноэтажного здания с размерами в плане 618×30м.2 В состав работ последовательно выполняемых при монтаже зданий входят: 1.4 Технологическая карта предусматривает выполнение работ с помощью крана КС0561. Контроль качества работ.
38674. Влияние редкоземельных элементов на оптические свойства германия 5.34 MB
  Поглощение в германии. именно кислородные комплексы оказывают наибольшее влияние на поглощение. В данной работе исследуется оптическое поглощение монокристалла германия легированного несколькими редкоземельными металлами на длине волны 106 мкм с целью выявления зависимости оптических свойств германия от влияния того или иного элемента и на основе этого вынести предположение о месте лантаноидов в таблице Менделеева. Поглощение – это ослабление излучения при прохождении через среду в результате взаимодействия его со средой и превращения...
38675. Использование игровых приемов при коррекции лексико-грамматических нарушений у детей старшего дошкольного возраста с ОНР III уровня 567.5 KB
  Изучение вопроса формирования навыка словоизменения и словообразования у детей с ОНР III уровня.2 Психологопедагогическая характеристика детей с ОНР III уровня 12 1.3 Развитие лексикограмматических навыков у детей старшего дошкольного возраста посредством игровых приемов16 ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ 19 ГЛАВА 2. Практическое исследование сформированности лексикограмматических навыков у детей старшего дошкольного возраста с ОНР III уровня.
38676. Построение структурной модели Софроницкого месторождения с использованием 3D моделирования 4.42 MB
  Литологостратиграфическая характеристика Геологический разрез Софроницкого месторождения Забродовской площади изучен по данным структурных поисковых и разведочных скважин до глубины 1780 м скважина №252 и представлен от четвертичных отложений до турнейских отложений. на структуре пробурено 4 скважины до отложений турнейского яруса: поисковые – 229; разведочные – 230 238 252. Максимально вскрытая глубина 1790 м скв. Все скважины – в консервации.
38678. Использование лекарственных растений в производстве макаронных изделий 1.43 MB
  Целью данной работы явилось изучение возможности использования лекарственного растительного сырья как источника биологически активных пищевых веществ (БАВ) при производстве макаронных изделий диетического назначения. В связи с этим изучено влияние сборов лекарственных растений на свойства клейковины и крахмала пшеничной муки, реологические показатели макаронного теста, качество готовых макаронных изделий
38679. АСПЕКТЫ ПСИХИЧЕСКОГО ВОЗДЕЙСТВИЯ ГЕОМЕТРИИ ФОРМЫ ПРОСТРАНСТВА ИНТЕРЬЕРА НА ЖИЗНЕДЕЯТЕЛЬНОСТЬ ЧЕЛОВЕКА 638 KB
  Стремления заказчиков архитектурных объектов к упрощению формы к ее удешевлению как постройки приводят к общему упадку архитектуры как духовной среды. Но пока осталась в большей степени за кадром тема взаимодействия человека и архитектурной формы как геометрического объема. Тем не менее знания о воздействии архитектурной формы в особенности же архитектурнопространственной формы как интерьерного пространства где современный человек проводит большую часть своего времени на его внутренний мир его психическое состояние очень важны для...
38680. ДЕФОРМАЦИЯ ТОНКОЛИСТОВЫХ ДЕТАЛЕЙ В ПРОЦЕССЕ ЛАЗЕРНОЙ РЕЗКИ 3.88 MB
  ТЕХНОЛОГИИ РАЗМЕРНОЙ ЛАЗЕРНОЙ ОБРАБОТКИ. Физические основы лазерной обработки. Физическая модель лазерной обработки. Физические явления ограничивающие качество лазерной обработки.