45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

14 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

53301. Хранение, использование и учет прекурсоров в химическом кабинете общеобразовательного учебного заведения 91.5 KB
  Прекурсоры вещества часто используемые при производстве изготовлении переработке наркотических средств и психотропных веществ включённых в Перечень наркотических средств психотропных веществ и прекурсоров утвержденный Постановлением Кабинета Министров Украины от 06. Согласно Закону Украины Об обороте в Украине наркотических средств присихотропных веществ их аналогов и прекурсоров от 15. № 503V необходимо вести строгий учет прекурсоров.
53302. Україна в подіях Північної війни. Повстання гетьмана Івана Мазепи 46.5 KB
  Повстання гетьмана Івана Мазепи. Виявити роль і значення Івана Мазепи в українському національно-визвольному русі. Внутрішня і зовнішня політика Мазепи. Мазепи.
53303. Національно-визвольна війна українського народу проти Речі Посполитої середини ХVІІ ст 64.5 KB
  Нагадую правила гри: за кожне порушення дисципліни викрики підказку журі має право зняти з команди від 2 до 5 балів. Кому розпочинати гру визначається за допомогою жеребкування Отже у нас все готове до початку КВК залишилось побажати тільки успіхів учасникам гри і оголосити склад журі. Оголошується склад журі Змагання сьогоднішнє я відкриваю 1 щиро усіх вас вітаю. Команда Ерудити Любить КВК наш дружний клас І оголосить засідання зараз Ось болільники а ось журі.
53304. Украинско-московский межгосударственный договор 1654 года. Продолжение Национально-освободительной войны 76.5 KB
  Цели: выяснить предпосылки и определить основные положения и значение украинско-московского договора 1654 года, а также дать историческую оценку событиям Национально-освободительной войны в 1654-1655 годах; развивать у учащихся жизненные умения и навыки: работать с историческими источниками и на основе их делать выводы и обобщения, давать оценку историческим событиям, высказывать свою точку зрения по отношению к ним...
53305. Україна в умовах десталінізації (1953 – 1964 рр.) 242.5 KB
  Назвіть події з історії України, які відбувалися після подій всесвітньої історії, визначених у першій колонці, але раніше, ніж події, визначені у третій колонці.
53306. НІКОПОЛЬЩИНА В РОКИ ДРУГОЇ СВІТОВОЇ ВІЙНИ 133 KB
  МЕТА: Проаналізувати події другої світової війни на Нікопольщині, удосконалювати навички самостійної роботи з додатковою літературою, картою, продовжити формувати вміння учнів, аналізувати, узагальнювати історичний матеріал, виховувати учнів у дусі патріотизму, гордості за бойові та ратні подвиги наших земляків.
53307. Порядок начисления и учета амортизации нематериальных активов 22.39 KB
  Амортизация – это процесс систематического, ежемесячного переноса стоимости на себестоимость продукции либо за счет собственных источников и накопление амортизационного фонда для замены изношенных экземпляров.
53308. Український національний рух на території Польщі (20-30-і рр. ХХ ст.) 85 KB
  Метод Припущення на основі запропонованих слів Учитель перераховує кілька слів із біографії Дмитра Донцова ідеолога право радикального руху. Учитель. Що далі Учитель. Учитель вислуховує пари із похвалою але не каже схожі вони чи ні на те що має бути почути.
53309. Україна в роки Другої світової війна (1939 -1945 рр.). Велика Вітчизняна війна (1941-1945 рр.) 131.5 KB
  Виховувати почуття гордості до історичного минулого України. Доповніть текст: Приєднання Західної України та Західної Білорусії до СРСР розпочалося після вступу Червоної армії на територію Польщі. Закон про включення Західної України до складу СРСР і воззєднання її з Українською РСР було прийнято: а Верховними Радами СРСР та УРСР у листопаді 1939 р.; б Народними зборами Західної України у жовтні 1939 р.