9.2 Zoektechnieken
In deze paragraaf worden enkele verschillende zoektechnieken gekarakteriseerd.
9.2.1 Basistypen zoektechnieken
Lees uit Stefik: paragraaf 2.1.2 (pagina 153 tot en met 156).
Stefik onderscheid vier basistypen zoektechnieken:
exhaustive search (uitputtend zoeken)
satisficing search (voldoende
zoeken)
optimizing search (optimaal zoeken)
resource limited search
(beperkt zoeken).
Hij geeft daarvan de karakteristieken en verschillen.
Op pagina 155 noemt hij nog een andere zoektechniek: due-process search. Dat zou vertaald
kunnen worden met overtuigend zoeken. Er wordt daarbij doorgezocht tot er een
overtuigende oplossing is gevonden.
In de meeste situaties waarin we een zoektechniek gebruiken, moeten we een compromis
sluiten tussen de efficiëntie en de volledigheid van het zoekproces.
Beschouw bijvoorbeeld een computerprogramma voor het spelen van schaak. Als we bij het
zoeken volledigheid zouden nastreven, zouden we alle spelvoortzettingen moeten berekenen
die mogelijk zijn bij een gegeven positie. Als we hiertoe in staat zouden zijn, zouden we
altijd de beste zet kunnen doen. Op dit moment bestaat er echter geen computer die dat
kan, en zon computer zal waarschijnlijk nooit gebouwd kunnen worden. (Merk op dat
indien zon computer zou bestaan, het schaakspel opgelost zou zijn. We zouden dan
kunnen bepalen welke zet tot winst zou leiden, op voorwaarde dat beide spelers vervolgens
altijd de beste vervolgzet doen. Het is overigens de vraag of er zon oplossing
bestaat.)
Omdat het ook in dit geval ondoenlijk is om alle mogelijkheden te doorzoeken, vanwege de
beperkte rekencapaciteit van mensen en machines, worden heuristieken
gebruikt. Een heuristiek bij computerschaak is een waarderingsfunctie die als doel heeft
in te schatten of een bepaalde zoekrichting vruchtbaar zal zijn. Een zet die leidt tot
stukwinst zal beter zijn dan een zet die leidt stukverlies. Moderne schaakprogrammas
gebruiken uitgekookte algoritmes voor de waardering van posities. Op grond van deze
waarderingen wordt die zet gedaan die leidt tot de positie met de hoogste waardering. Er
is echter geen garantie dat de gekozen zet inderdaad de beste is. De beste zet kunnen we
alleen bepalen door alle mogelijkheden te bekijken, dus wanneer we volledigheid hebben.
9.2.2 Zoekruimtes representeren
Lees uit Stefik: paragraaf 2.1.3 tot en met 2.1.5 (pagina 156 tot en met 159).
Als bomen worden gebruikt om zoekruimtes mee te representeren, kunnen oplossingen knopen in de boom zijn (eventueel alleen de bladeren), of de paden van de wortel van de boom naar de betreffende knoop. Beide mogelijkheden zijn in essentie equivalent, omdat er altijd maar één pad is van de wortel naar een bepaalde knoop.