Topic 3 & Topic 4 Flashcards
Leg uit wat state space representation inhoudt en wat de concepten zijn:
State space representation:
Manier om problemen te modelleren zodat een algoritme op zoek kan gaan naar de oplossing van dat probleem.
State:
Je moet de toestand van een probleem voorstellen in een programmeertaal.
Goal:
Je moet de doel/doelen efficiënt kunnen herkennen dus een volledige beschrijving opstellen van de toestanden waarin je het spel wint.
Move:
Een zet die je kan doen vanuit een bepaalde spelsituatie. Meestal zijn er meerdere moves nodig.
Leg uit welke onderdelen/aspecten moeten behandeld worden bij een state space representation:
- Een manier vinden om een spelbordsituatie ondubbelzinnig voor te stellen.
- Procuction rules: worden gebruikt om de mogelijke rules te vinden vanuit een bepaalde spelsituatie
- Matching: manier om te controleren of een regel van toepassing is of niet.
- Een toestand specificeren waar het doel is bereikt.
- Control problem: Vanuit elke situatie kunnen vinden welke regels/moves we het best toepassen om het spel te winnen
Leg beknopt uit wat een search tree is:
Wat bepaalt de grootte van de spelboom?
Hoe kan de grootte beperkt worden?
Voor elke state space representation kunnen we een zoekboom opstellen.
Als we vanuit de initiële toestand alle mogelijke zetten bekijken en vanuit elke mogelijke zet opnieuw alle mogelijke zetten berekenen bekomen we een zoekboom.
De opeenvolgende moves die genomen worden vormen een pad in de spelboom.
Een zoekboom kan al snel heel groot worden.
- De grootte van de spelboom bepaalt voor een deel de complexiteit van het spel.
- Lussen/cycles (opeenvolging van moves waardoor je terug in een vorige spelsituatie terecht komt) niet toelaten kan de grootte van de boom beperken
Hoe zit het met de zoekboom van de 8-puzzle en waar hangt de grootte eigenlijk van af?:
De zoekboom van 8-puzzle wordt al snel heel groot, zelfs voor een simpel spel als 8- puzzle.
- 9!/2 dus 181.440 nodes
- Grootte is afhankelijk van de branching factor
o Hoeveel regels zijn er gemiddelde per toestand?
o Hoeveel moves kun je maken vanuit elke toestand?
o 8-puzzle: 1,8
o Chess: 35
o Go: 250
Leg het verschil tussen forward en backward reasoning uit.
Bij forward reasoning start men vanuit de initiële toestand en zoekt men een weg naar een doeltoestand.
Bij backward reasoning start men vanuit een doeltoestand en probeert men een pad te vinden naar de starttoestand.
Verschil tussen blind search en heuristic search.
Bij blind search zoek je blindelings naar een oplossing zonder rekening te houden met de kosten die een pad met zich teweeg brengt. Bij heuristic search wil je de optimale pad vinden.
Leg de twee soorten ‘kosten’ uit
1) Computational cost
De kost die nodig is een pad te vinden, dit is gelijk welk pad, niet noodzakelijk een optimaal pad. (De kost die nodig is om het algoritme te laten lopen)
2) Travel cost:
De kost om een pad te volgen
Backtracking
We gaan bij depth first search zo diep mogelijk tot we niet meer verder kunnen. Het terugkeren naar een bovenliggende node omdat je niet meer verder kan = backtracking.
