45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

14 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

15065. Қайта өрлеу дәуіріндегі итальян әдебиеті 42.5 KB
  Қайта өрлеу дәуіріндегі итальян әдебиеті Данте Данте Алигьери май 1265. Флоренция 14.9.1321. Ровенна итальян ақыны. Дворян әулетінен шыққан. Жасынан теологиямен философиямен астрономиямен орта ғ
15066. Қараша, желтоқсан мен сол бір-екі ай 18.9 KB
  Қараша желтоқсан мен сол бірекі ай Композициялық кеш 58сыныптар аралығында 1жүргізуші: Тақырыбы: Қараша желтоқсан мен сол бірекі ай Мақсаттары: Оқушыларға табиғаттың құдіреттілігін таныта отырып жыл мезгілдерінің әсемдігін сезіне бағалай білуге баул...
15067. Қобланды батыр жыры 77 KB
  Қаһармандық рух қайта түледі Қобланды батыр жыры Немістің әйгілі ғалымы Альфред Вебер былай деп жазады: €œОрталық Азиядан шыққан көшпелі халықтардың Қытай Үндістан және батыс елдеріне басакөктеп жетуі ежелгі дүниенің осынау ұлы мәдениеттері көшпелілерден жы...
15068. Қобыланды батыр жыры 44 KB
  ҚОБЫЛАНДЫ БАТЫР Мұхтар Әуезов Қазақ халқының эпосында батырлар жыры ең бір мол сала. Бұл дастандар көбінесе сонау бір бағы заманда Орта Азияны Қырым мен Еділ бойын жайлаған көшпелі тайпалар бастан кешірген нақтылы тарихи оқиғалардың поэтикалық көрінісі болып
15069. Қозы Көрпеш - Баян сұлу жырындағы Баян образының жасалуы 53.5 KB
  ӘОК 894.342 ҚОЗЫ КӨРПЕШБАЯН СҰЛУ ЖЫРЫНДАҒЫ БАЯН ОБРАЗЫНЫҢ ЖАСАЛУЫ А. Көбетаева Бауыржан Момышұлы атындағы № 45 қазақ классикалық гимназиясы Тараз қ. Қозы КөрпешБаян Сұлу жырының тарихымыздың қай дәуірінде пайда болғандығы жөнінде ғалымдар
15070. Құтты білік ескерткішінің тарихи танымының қалыптасуының көркем-идеялық әсері 50 KB
  ҚҰТТЫ БІЛІК ЕСКЕРТКІШІНІҢ ТАРИХЫ ТАНЫМЫНЫҢ ҚАЛЫПТАСУЫНЫҢ КӨРКЕМИДЕЯЛЫҚ ӘСЕРІ Ж.Абеуова Б.Х.Тажибаев Керімбай атындағы №12 мектепресурстық орталығыТараз қ. Ежелгі Түркістанның батысы мен шығысында бірдей ІХ ғасырдан бастапақ ықпалды іргелі елдік құрған Қа...
15071. Қыз Жібек жырындағы салт-дәстүрлер 91 KB
  Қыз Жібек жырын меңгерте отырып, мазмұнына талдау жасату, жырдағы кедесетін салт-дәстүрлер,олардың қазақ халқының тұрмыс-тіршілігіндегі, бала тәрбиесіндегі орны туралы білім қалыптастыру.
15072. Қызыл империяға құлдық ұрған аударма. Көшпенділер 1.31 MB
  Нұрсәуле Рсалиева Қ.А.Ясауи атындағы ХҚТУ Тіл маманы Нұрсәуле Рсалиева Мақсұтқызы зерттеу жұмыстарын І.Есенберлиннің Көшпенділер трилогиясының ағылшын тіліндегі аудармасына арнап шығарманың орыс тіліндегі және орысша нұсқасынан жасалған ағылшын ті
15073. М. Әуезовтың Абай жолы романының әдеби көркемдігі 74 KB
  М. Әуезовтың Абай жолы романы Алаш қайраткерлері ішінде коммунистік террордан тірі қалған жалғыз қазақ Мұхтар Әуезов еді. Ол ұлы толқынның рухани аманатын көркем әдебиетте толық қалдырған бірденбір қаламгер. Бұл идея ең алдымен оның басты шығармасы €œАбай жолы