45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

13 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

57483. Виховна година, Моя Батьківщина - Україна 59 KB
  Мета: поглибити знання учнів про Україну; прищеплювати любов до рідного краю; розширити зміст поняття громадянин України; розвивати мовлення учнів; виховувати патріотичні почуття приналежності до українського народу.
57484. Сценарій літературного вечора «З Україною в серці» 1.31 MB
  Ведучі. Петриненко Ведучі. Україна Ти для мене диво І нехай пішов за роками рік буду завжди я горда і вродлива з тебе дивуватися навік На екрані карта України Ведучі. Ведучі.
57485. Welcome to Ukraine 55 KB
  The aims: Practical aims: to teach the new vocabulary, by the end of the lesson pupils will have revised the information they have learned about Ukraine, will have recollected some facts about our country by doing different tasks...
57486. Ukraine is our native country 73.5 KB
  The aims: to repeat the learnt vocabulary; to revise the information pupils have learnt about Ukraine; to recollect some facts about our country by doing different tasks: making up sentences and monologues, writing pass-letters;
57487. Кількість, густота, природний рух населення України 99 KB
  Після цього уроку учні зможуть: ознайомитись з кількістю населення України і її зміною в часі; давати визначення поняттям природний приріст міграція розкривати вплив природних історичних умов на розміщення населення на території України...
57489. Ukraine and Great Britain 1.86 MB
  Today we have unusual lesson. It’s a Presentation Lesson and its topic is “Differences and Similarities of Ukraine and Great Britain”. The aim of our lesson is to improve our knowledge, to learn more and broaden our outlook, to watch presentations, to play games.
57490. Welcome to Ukraine! 169.5 KB
  Today we have an unusual lesson. We are going to prepare for journey around Ukraine. We’ll travel next time. We’ll go by bus. But first of all we need tickets. You shouldn’t pay money for these tickets. You should answer some my questions to get a ticket. Let’s start.
57491. Послевоенное восстановление и развитие Украины (1945 - начало 1953 года). Голод 1946-1947 гг 65.5 KB
  Давайте мы пополним этот коллаж нарисовав свой символ голодоморов. Приложение №1 Документ №1 29 августа 1946 года былю официально объявлено что в связи с засухой в ряде областей СССР и сокращением государственных...