Выборочные продления Краткая характеристика расширений

Добавлено Дата: 8 December, 2010 категория: Игры, Теория

В полном широтном поиске, который мы рассматривали, глубина поиска задавалась при первом вызове рекурсивной функции и уменьшалась в каж­дом узле на 1. Таким образом, мы осуществляли полный перебор на неко­торую фиксированную глубину. Мы рассмотрели также устройство форси­рованного варианта, который вызывался при Depth = 0 и сглаживал эффект горизонта. Форсированный вариант просчитывал дальше наиболее сильные перемещения и давал приблизительную оценку позиции горизонта. Допус­тим, что при минимальном размере дерева перебора, т. е. при оптимальном порядке перемещений, для углубления счета на глубину N+1 нам необхо­димо рассмотреть в 20 раз больше позиций, чем при счете на глубину N. Это довольно приблизительно, но нам для рассуждений нужно отталкивать­ся от каких-то величин. Существует мнение, что увеличение глубины счета на один полуход повышает силу игры программы на разряд. Может, не сто­ит ломать голову над разными ухищрениями, а просто подождать, пока процессоры станут мощнее в 20 раз. Мы сможем считать на 9 полуходов, потом еще в 20 раз — мы сосчитаем на 10 полуходов. Бывают тактические последовательности, которые программа должна просчитывать значительно глубже. Например, если на доске существует форсированная угроза королю, то может потребоваться считать на 14 полуходов. Гроссмейстеры просчиты­вают некоторые варианты на 20 и более полуходов. Вряд ли мощность про­цессоров когда-либо возрастет до такого уровня, да и программы желатель­но писать сейчас, а не через 10 лет. Человек, когда просчитывает некоторые варианты, руководствуется множеством критериев, зависящих от его опыта. Он может просчитать ситуацию очень глубоко, проанализировав при этом минимальное количество позиций. Несмотря на то, что моделировать мыш­ление шахматиста мы не можем, существуют некоторые строки игры, про­счет которых можно продолжить по совершенно формальным признакам. Возникла простая идея — не сокращать глубину просмотра при некоторых ходах. Мы можем считать на 6 полуходов, но некоторые варианты будут рассмотрены значительно глубже. При каких же ходах не сокращается глу­бина счета? Если мы говорим о шахматах, то это, прежде всего, шах. При шахе игра как бы замирает и требует от противника немедленного ответа. Замедление счета при этом тоже минимальное, т. к. число легальных ходов под шахом ограничено, и узел будет обсчитан очень быстро. Продление все­го лишь шахов резко увеличивает силу игры программы. Считая на 6 полу­ходов, она способна обнаружить глубокие форсированные маты и другие комбинации, основанные на угрозе королю и приводящие к выигрышу ма­териала. Пример функции счета, продлевающей шахи:

Читать »

Организация автономных тестов

Добавлено Дата: 8 December, 2010 категория: XSLT

Задача

Требуется организовать тесты, чтобы упростить процедуру тестирования.

Решение

Посмотрите, как в рецепте 15.4 мы внедрили тестовые данные в таблицу сти­лей. В каждом тестовом элементе имеется атрибут num, а правильный результат за­писывается в атрибут ans. Затем управляющая программа извлекает тестовые эле­менты, выполняет тест и сравнивает ожидаемый результат с получившимся. Важно то, что управляющая программа ничего не выводит, если тест прошел успешно.

Читать »

Опрос XML-документа – Введение

Добавлено Дата: 8 December, 2010 категория: XSLT

Эта глава посвящена рецептам использования XSLT как языка запросов для XML. Под запросом к XML понимается извлечение информации из одного или нескольких XML-документов, которая отвечает на вопросы о хранящихся в этих документах фактах и существующих между ними отношениях. Можно провести аналогию между запросом к XML на языке XSLT и запросом к реляционной базе данных на языке SQL.

Читать »

Дробный Depth

Добавлено Дата: 6 December, 2010 категория: Игры, Теория

Нужно просчитывать глубже многие ходы, но это может привести к взрыву дерева поиска, и только шахи являются стопроцентно корректными расши­рениями на любой глубине. Возникла следующая идея: делать Depth дроб­ным. В каждом узле Depth уменьшается не на 1, а на 4. Начальное значение Depth тоже равно глубине просчета, умноженной на 4. Таким образом, в за­висимости от нашего представления о правдоподобности данного хода, мы можем при одних ходах увеличивать Depth на 4 (при шахах), а при других — на меньшую величину. Приведем примерный список расширений:

Читать »