14. Előadás - Klasszikus mesterséges intelligencia algoritmusok
===============================================================

A problémateret egy gráfként reprezentálhatjuk.

* A játék állapota a gráf egy pontja.
* Minden lehetséges lépés egy-egy élt ad egy szomszédos pontba.
* Minden játékállapothoz hozzá rendelhetünk egy jósági értéket (a játék értékét az adott játékos szemszögéből).

Zéró összegű játékról beszélünk, hogy ha a két játékos összpontszáma nullát kell, hogy kiadjon.

Sudoku
~~~~~~

Az egyszerűbb implementáció esetében a megoldást úgy keressük, hogy végig próbálgatjuk az üres helyeken mind a 9 számértéket.

* A rekurzív implementáció a kézenfekvő.
* Szekvenciális esetben igyekszünk kerülni a tábla másolását.
* A rekurzív hívások párhuzamosan kiértékelhetők, hogy ha van saját másolatuk a tábláról.

Amőba
~~~~~

Naiv implementáció:

* Minden mező esetében a jósági értéket az alapján kapjuk, hogy oda egy szimbólumot helyezve mennyi lehetőségünk lesz a későbbiekben 5-öt kirakni.
* Az algoritmusban vannak súlyparaméterek, amelyek azt mutatják, hogy mennyi az értéke az 1-től 5-ig a kirakott részeknek.

Fában való keresés:

* Minden játékállapotból minden játékállapotba a lépések mentén élek vezetnek. Mivel nincs a játékban visszafelé lépés, ezért ez egy fát eredményez.
* A fa leveleiben vannak a nyert, vesztett és a döntetlen játszmák.
* Meg szeretnénk becsülni, hogy az adott részfában ezek száma mennyi.
* A sok lépési lehetőség miatt a fa terebélyes, nem praktikus minden ágon ténylegesen végig haladni.

Párhuzamosítási lehetőségek:

* A naiv implementáció esetén a paraméterek becslése szimulációval végezhető. Egy-egy paraméter kiértékelése párhuzamosan elvégezhető.
* A szóbajöhető mezőkre a jósági érték kiértékelése párhuzamosan elvégezhető. (Egyidejűleg a maximum kiválasztására is van lehetőség.)

Kérdések
--------

* Mit jelent az, hogy egy játék zéró összegű?

Feladatok
---------

* Adjunk hatékonyabb számítást a Sudoku tábla érvényességének ellenörzéséhez!
* Becsüljük meg az Amőba játék optimális paramétereit!