Problém rozestavění osmi dam na šachovnici ­ alternativní řešení metodou hill-climbing
Úloha č. 4 pro cvičení k předmětu Vybrané kapitoly z umělé inteligence
Zadání: Implementujte v libovolném programovacím jazyce heuristiku hill-climbing (lezení do kopce), zmíně-
nou na přednášce, pro uspořádání osmi vzájemně se nenapadajících dam na šachovnici 8x8. Své řešení otestujte
na příkladu uvedeném níže a dále navrhněte ještě nějakou jinou testovací pozici (alespoň jednu); můžete využít
data z minulé úlohy č. 3, kde byl tentýž problém řešen pomocí metody min-konflikt. Vyhodnoťte svá řešení--
např. zjistěte průměrný počet kroků pro nalezení výsledku, nárůst jejich počtu při výskytu 2, 3 nebo více kon-
fliktů, apod. Tato úloha je v podzimním semestru 2005 poslední.
Výsledek úlohy pošlete přes e-mail na adresu zizka@cba.muni.cz obdobně jako pro úlohy č. 1, 2 a 3; subjekt
e-mailu bude obsahovat text HILL a jméno a příjmení autora řešení (např. HILL BOBBY FISCHER). V popisu
svého řešení úlohy uveďte obdobně to, co v popisu řešení úlohy č. 3. Podmínky odevzdání, včetně procentového
ohodnocení, jsou stejné jako u úloh č. 1, 2 a 3; datum odevzdání je jiné:
Termín je do půlnoci v sobotu 31. prosince 2005 (lze samozřejmě i dříve).
Pozn.: hill-climbing je v principu jednoduché hledání cesty k řešení, kdy agent vidí pouze do omezené vzdále­
nosti, které následující stavy má k dispozici, a zvolí jako další stav ten, který momentálně vypadá nejslibněji
z hlediska zlepšení situace, v níž se nachází (greedy search, lačné vyhledávání). Metoda patří k nejzákladnějším
tzv. lokálním vyhledávacím technikám: současný stav (uzel) je nahrazen stavem (uzlem) tvořeným nejlepším vi-
ditelným sousedem (uzlem), který má ze všech viditelných sousedů nejvyšší hodnotu. Globální maximum vidět
není, nejlepší momentálně viditelný soused může být maximem lokálním a obecně hrozí uvíznutí v lokálním ex-
trému neznámé funkce. Další nebezpečí hrozí v případě, kdy okolní viditelní sousedé (tj. nejbližší stavy) mají
všichni stejné vyšší hodnoty, takže nelze jednoznačně určit, kterým směrem se má agent vydat--cílem je "lézt
do kopce", tj. zvyšovat hodnotu dosud nalezeného řešení (optimum je v globálním extrému, jehož nalezení není
zaručeno). Také když se objeví "hřeben" pohoří (směřující nahoru), vede to obvykle k sekvenci lokálních extré-
mů. Hill-climbing je cyklus, který posouvá agenta neustále do nějakého dalšího stavu s vyšší hodnotou.
Ukončení vyhledávání není jednoznačné--agent může skončit, pokud nevidí nikde kolem sebe lepší stav, než
v jakém právě je, ale to nemusí znamenat, že lepší stav není: např. ocitne-li se na "náhorní planině" a vlivem
"zamlženosti" krajiny (prohledávaného prostoru) nevidí, že někde je ještě možné šplhat dál vzhůru. Heuristika
nepoužívá vyhledávací strom (není zapotřebí rozsáhlá paměť), je rychlá, ale často uvázne v lokálním extrému.
Existují různá vylepšení, např. pro umělé neuronové sítě, ale zcela odstranit všechny nedostatky nelze.
XABCDEFGHY
8-+-+-+-+(
7+-+-+-+-'
6-+-+-+-+&
5+-+q+-+-%
4q+-+q+-+$
3+q+-+q+q#
2-+q+-+q+"
1+-+-+-+-!
xabcdefghy
Jedna z možných pozic s mnoha
napadajícími se dámami
(h = 17 napadajících se dvojic)
XABCDEFGHY
8-+-+-+q+(
7+-+-wW-+-'
6-wW-+-+-+&
5+-+q+-+-%
4-+-+-wW-+$
3+-+-+-+q#
2-+q+-+-+"
1wW-+-+-+-!
xabcdefghy
Příklad uváznutí v lokálním extrému
po nalezení zlepšené pozice
(h = 1 napadající se dvojice)