45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

14 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

53783. Чтение примеров на умножение. Название чисел при умножении. Составление таблицы умножения числа 2. Задачи на действие умножения 127.5 KB
  ЦЕЛЬ: упражнять детей в чтении и записывании примеров на умножение; учить заменять действие сложения одинаковых слагаемых действием умножения а действие умножения действием сложения; ознакомить с названиями компонентов при умножении; ознакомить с таблицей умножения числа 2; развивать математическую речь логическое мышление умение анализировать сопоставлять и делать выводы. Сегодня мы с вами продолжаем знакомиться с дествием умножения.
53784. Конспекти уроків з української літератури 117 KB
  Той хто перший виконав завдання намагається здобути більшу кількість балів. Урок – гра “Перших 12 балівâ€ Відбіркове питання: записати залежно від обсягу починаючи з найменшого: новела роман вірш оповідання романепопея. 5 балів:: â€Кам’яний хрест†В. 6 балів: До інтимної лірики належить така поезія: Хто автор а “Як я люблю оті години праціâ€; б â€œГімнâ€; в “І всетаки до тебе думка линеâ€; г “Тричі являлась мені лю ...
53785. Конспекти уроків «Музичне мистецтво» 209 KB
  Заглибимося в далеке минуле і поміркуємо, як виник цей вид мистецтва. Можливо музика народилася від співу пташок або дзюрчання струмка, а може, - від ритмічної праці людини, магічних обрядів, або від слова, мелодійної мови людини? Це було дуже давно, і ми можемо лише припустити, як жила тоді первісна людина. Цікаво, що наштовхнуло її на винахід музичних інструментів?
53786. Обобщение и систематизация знаний и умений по теме Квадратное уравнение и его корни 97 KB
  Учащиеся должны знать: определение квадратного уравнения; формулы дискриминанта корней квадратного уравнения; зависимость между значением дискриминанта и количеством корней квадратного уравнения. Учащиеся должны уметь: распознавать квадратные уравнения среди других уравнений; решать неполные квадратные уравнения по формуле корней квадратного уравнения; находить сумму и произведение корней приведенного квадратного...
53787. Конспекты занятий по математике 1.57 MB
  Из курса геометрии мы знаем что sin А = а соs А = . Затем выводилось основное тригонометрическое равенство: cos2 А sin2 А= = 1 Но есть недостатки этого метода. Если точка М числовой окружности соответствует числу t то абсциссу точки М называют косинусом числа t и обозначают cos t а ординату точки М называют синусом числа t и обозначают sin t слайд 5. Итак если М t = М х; у то х = cos t у= sin t слайд 5.
53788. Конспекты уроков русского языка 7 класс по учебнику Ладыженской Т. А. 2.85 MB
  Цели: систематизировать знания обучающихся о пунктуации повторить теоретический материал о разделах лингвистики закреплять умение выполнять синтаксический разбор предложения составлять схемы предложений; развивать внимание память такие операции мышления как анализ синтез обобщение; воспитывать интерес к предмету. Какие знаки препинания могут стоять в конце предложения Докажите на примерах из текста. С каким знаком препинания в конце предложения мы не встретились Придумайте...
53789. В гостях у Айболита. Посвящение в Айболята 503 KB
  Доктор Айболит: Ребята я получил письмо показывает его и зачитывает.– Ребята а вы знаете мы ведь чуть не опоздали к вам вы уж нас простите пожалуйста.– Ребята а как вы догадались что я доктор Айболит Дети: У вас белый халат. Доктор Айболит: Молодцы ребята Вы великолепно справились с первым испытанием.
53790. Баскетбол 96 KB
  Совершенствование техники ведения мяча: варианты ведения мяча без сопротивления и с сопротивлением защитника (обычное ведение и ведение со сниженным отскоком).
53791. КОНСПЕКТЫ УРОКОВ ПО ГЕОГРАФИИ 569.5 KB
  Её можно выразить количеством лет на которые должно хватить данного ресурса либо его запасами из расчёта на душу населения. Прочитайте текст учебника с 29 – 32 и ответьте на вопросы: Какова структура земельного мирового фонда Какие земли представляют наибольшую ценность в каких природных зонах сосредоточена большая часть обрабатываемых земель Какова доля пашни в земельном фонде планеты Какие процессы оказывают влияние на структуру земельного фонда планеты В чём заключается истощение земель Почему обеспеченность...