45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

14 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

22885. Алгоритм знаходження НСД 71 KB
  Поділимо на з залишком і стст якщо то процес закінчуємо інакше ділимо на при цьому стст якщо то процес закінчуємо інакше лідимо на і так далі. Оскільки на кожному кроці степінь залишку зменшується то за скінченну кількість кроків процес закінчиться.
22886. Теорема про найбільший спільний дільник 149 KB
  Доведення Припустимо і ненульові многочлени. Позначимо через таку множину многочленів зрозуміло що . Якщо і довільний многочлен який не обовязково належить то і .
22887. Теорема про найбільший спільний дільник (доведення іншим способом) 90 KB
  Нехай і для визначеності стст. Покажемо що стст. Припустимо що стст тоді стстст що неможливо. Нехай і взаємнопрості тоді існують многочлени і такі що причому і можна вибрати так що стст стст.
22888. Схема Горнера та її застосування 109 KB
  Прирівняємо коефіцієнти при відповідних степенях маємо: Приклад застосування.
22889. Незвідні многочлени та основна теорема про подільність многочлена 63 KB
  Аналогічним чином в кільці многочленів є незвідні многочлени . Многочлен є незвідним над полем якщо з того що і слідує що степінь одного із многочленів рівна нулю тобтохоч один із многочленів рівний . Аналогічно основній теоремі арифметики будьякий многочлен відмінний від можна розкласти в добуток незвідних многочленів.
22890. ОБЛІК ДОВГОСТРОКОВИХ АКТИВІВ 120 KB
  Склад, класифікація і оцінка довгострокових активів. Методи розрахунку і облік амортизації основних засобів. Облік надходження і вибуття основних засобів. Облік природних ресурсів та їх виснаження.
22892. Рівність многочленів 82.5 KB
  Два многочлени і вважаються рівними аналітично якщо вони рівні як відображення . Два многочлени і над полем рівні тоді і тільки тоді коли вони рівні аналітично і алгебраїчно. Доведення Зрозуміло що якщо многочлени і рівні алгебраїчно то вони рівні і аналітично.
22893. Кратність коренів многочленів 47 KB
  Якщо є коренем цього многочлена то за теоремою Безу . Корінь ненульового многочлена коренем кратності якщо ділиться на і не ділиться на . Число коренів даного многочлена з урахуванням їх кратності не перевищує степеня даного многочлена. Доведення Припустимо корені многочлена кратності відповідно .