Лекция 3 - 19.10.2010

страницата се нуждае от дописване/преглеждане


При задачата за удовлетворение (CSP) идеята е да се удовлетворят пространството на търсене и ограниченията. В нея обхождането на графа (пространството) може да се представи посредством дървовидна структура. Всяка стъпка от обхождането представлява премахване на ограничения - първо разглеждаме върховете, а след това техните стойности. Възможно е премахване на върхове. Крайната цел е да получим алгоритъм, работещ за "нормално" време. Могат да се използват итеративни алгоритми за решаването на такава задача. Те ще се стремят да минимизират броя на конфликтите, свеждайки го накрая до 0 (надяваме се). Това ще стане чрез промяна стойностите на променливите, които не удовлетворяват ограниченията.

CSP е специален вид задача. Стандартен вид търсене е в дълбочина (DFS). При неговото разгръщане може да се проверява един ход напред (в зависимост от конкретната задача) с цел в по-ранен момент да се предотврати неудовлетворяването на някои ограничения и последващото връщане назад. Започва се от случайно оцветяване, след което се търсят конфликти и се следи за ограниченията, като се използват техники от сорта на генетични алгоритми и hill-climbing.'

В общия случай се генерира едно случайно решение и се определя броят конфликти. След това се предприемат стъпки за намаляването на този брой. Ограниченията са наложени върху променливи и връзките между тях - случайното решение представлява някакви начални стойности на всички променливи, след което на всяка стъпка те се променят. Различни възможни оптимизации са евристики за подобряване времето на търсене (решаване); методи за ограничаване фронта на разрастване на задачата; техники за ограничаване пространството на търсене.

[Всичко това май е обобщаване/припомняне на казаното в предишните лекции?]

Game playing

Играта е естествен начин за обучение. Игрите могат да се класифицират по следния начин:

детерминистични (определени в пространството) случайни (шанс)
пълна информация (observable)
непълна информация

При нея имаме феномени като непредсказуем опонент (чиито цели са противоположни на нашите) и времеви ограничения. В игрите с двама играчи всеки се стреми да максимизира своята печалба и да минимизира тази на противника1.

При строенето на дърво се конструира процедура, която в единия случай минимизира, а в другия максимизира [кое - нямам идея]. Една задача е:

  • complete - ако дървото е определено (небезкрайно). Пример: шах
  • Optimal - ако се играе срещу оптимален (възможно най-добър) противник

minmax

Детерминистична игра с пълна информация. Двете функции се викат една друга, като едната максимизира, а другата минимизира. Задачата е крайна. Играта е оптимална срещу оптимален играч - който не прави много грешки. Фронтът, който бива разширяван, е линеен, търсенето - дълбочинно, времето - линейно (?).

  • $\alpha-\beta$ отсичане

Техника, която следи строенето на дървото. $\alpha$ е най-добрата стойност от гледна точка на максимален (?) играч, $\beta$ - най-добра от гледна точка на минимален (?). "Окастряме" "неперспективните" клонове на дървото - това окастряне не променя крайния ход на играта, а значително подобрява времето на изпълнение. Въвежда се метаразсъждение за самите разсъждения в играта.

Обикновено разполагаме с ограничение на ресурси (например време, памет). Затова не можем да построим пълно дърво. Използваме оценъчна функция, която ни помага да търсим до определена дълбочина - на нея могат да се предвидят няколко хода напред и да се определи по кой клон да се продължи. Важно е фунцията/трансформациите да са монотонни (?). Също така, важна е наредбата, а не размерът на дървото.

Недетерминистични игри (хвърляне на зарче, раздаване на карти, …)

Между min и max се вкарва фактор, който усложнява дървото. Важно е каква евристика (оценъчна функция) ще бъде измислена, тъй като тя определя размера. Може да се използват вероятностни решения в различните случаи, след което да се оцени най-доброто решение и да се избере.

При игрите с непълна информация сме в информационно състояние (?) - целим да получим повече информация, а не толкова по-голяма печалба (пример: блъфиране). Перфектното положение не винаги е постижимо. Добре е да се мисли какво да се мисли2. Оптималните решения зависят от информационното, а не от реалното състояние.

Knowledge representation (представяне на знанията)

Важен проблем е представянето на известните ни знания по такъв начин, че да може да се "разсъждава" с тях. Знанията са наличните факти, а също така и самата процедура. Представянето на знанието трябва да го свързва с цялостната картина, затова избирането на предсредставянеаьяаяьатавяне (репрезентация) е съществено.
Освен наличното до момента знание, необходимо е да се създаде механизъм за трупане на знания - тоест, обучение (learning mechanism). За различните ситуации съществуват различни представяния - за част от ситуациите са измислени най-подходящи представяния, а за други класове все още не са известни. Пример за представяне на знания е невронната мрежа.

Ще въведем 4 различни формализма за представяне на знания.

Логики

Характеризират се с точно определен синтаксис и с ограничени възможности за представяне в сравнение с произволен естествен език. Синтаксис - това е начинът на конструиране на изречения на логиката, използваните символи и правилата, по които ги пишем.

UNFINISHED BUSINESS

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License