45337

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

Доклад

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

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

Русский

2013-11-16

36.5 KB

14 чел.

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

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

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

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

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

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

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


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

30

900

27 000

810 000


 

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

42883. Химическая металлизация печатных плат 1.32 MB
  И так как вытравливается только этот минимальный слой около 3 мкм то величина подтравов минимальна до 2 мкм что позволяет воспроизводить проводники малой ширины. Поэтому в методе необходимо применять фоторезист толщиной около 30 мкм. Затяжкой Тентинг –метод с общей металлизацией поверхности заготовки Слои 1 2 3 4 5 18 мкм 18 мкм 18 мкм Фольга 3 мкм 6 мкм 35 мкм Общая металлизация поверхности 30 мкм 40 мкм 40 мкм 50 мкм Фоторезист 25 мкм 35 мкм 35 мкм Металлизация рисунка 15 мкм 15 мкм Металлорезист 3 мкм 18 мкм 24 мкм 53 мкм Глубина...
42884. Разработка программы для построения графика временной функции в реальном и машинном времени 439 KB
  Создание MS-DOS QuickBASIC (сокращенное обозначение – QB) в середине 80-х годов произвело настоящую революцию в мире BASIC, результатом которой было то, что впервые этот язык занял достаточно прочные позиции среди средств разработки серьезных прикладных систем. В QuickBASIC в достаточно полной мере реализованы идеи структурного и модульного программирования, возможности использования процедур и функций.
42885. Разработка обучающей программы по планированию перемещения артиллерии при заданных рубежах: готовности; начала перемещения; выхода в атаку 247.06 KB
  После запуска следует выбрать какие рубежи заданы Для примера в варианте расчета при заданном рубеже начала перемещения дана схема отображающая перемещения войск в зависимости от введенных данных.
42886. Поиск и индексация в Web. Интернет-каталоги 1004 KB
  Помимо глобального поиска в пространстве Интернет существует также проблема локального поиска, т.е. поиска в пределах одного сайта или портала. Существуют готовые решения, однако для поиска внутри сайта иногда требуется более точная настройка и свои, индивидуальные, алгоритмы, которые будут осуществлять более точный и быстрый поиск по тем данным, с которыми работает сайт. Одним из главных недостатком стандартных решений от Google или Яндекс, например, также является низкая скорость обновления информации о страницах, т.е. индексации.
42890. Дивідендна політика в банку та методи її реалізації 101.48 KB
  Дивідендна політика – це сукупність заходів які здійснюються банком і спрямовані на прийняття рішень із нарахування та виплати дивідендів власникам акцій цього банку. Використання коштів на виплату дивідендів акціонерам – перший із двох основних шляхів розподілу прибутку банку після оподаткування другим є спрямування коштів на інвестиції для подальшого розвитку банку що приводить до збільшення майбутніх грошових потоків. Перший підхід носить назву Теорія нарахування дивідендів за залишковим принципом . Іншими словами сума виплачених...
42891. Анализ финансового состояния ООО «Алексеевское» Горьковсвского района Омской области 170.8 KB
  Огромное значение в этом вопросе имеют такие понятия рыночной экономики как деловая активность платежеспособность и кредитоспособность предприятия порог рентабельности запас финансовой прочности запас безопасности степень риска эффект финансового рычага и др. В процессе снабженческой производственной сбытовой и финансовой деятельности происходит непрерывный процесс кругооборота капитала изменяется структура средств и источников их формирования потребность в финансовых ресурсах и как следствие финансовое состояние предприятия....