8. heti jegyzet (2014.11.27.)

Órai anyag:

Zéró-összegű játékok. Játékfák. Minimax, negamax.

Egy asztalon n db golyó van. Két játékos felvátva vesz le 2, 3 vagy 7 db golyót.
Ha egy lépés negatív golyószámot eredményezne, akkor az nem léphető meg.
Ha valaki nem tud már lépni, akkor veszít, és ellenfele nyer.
Pszeudokód, mely kiszámítja, hogy (optimális játékot feltételezve) a kezdő játékos nyerni vagy veszíteni fog:
lepes[]={2, 3, 7}
for i:=0 to n
| t[i]:=false // a t tömb n+1 elemű
| for j:=0 to 2
| | if i-lepes[j]>=0 && t[i-lepes[j]]==false
| | | t[i]:=true
if t[n]
| print("nyer")
else
| print("veszít")


Házi:

(Az órán feladott házi lehet, hogy nagy falat lenne, így kitűztem egy könnyebbet.)

Egy asztalon n db golyó van. Két játékos felvátva vesz le egy vagy több golyót.
Ha páratlan számú golyó van az asztalon, akkor 1 vagy 2 golyó vehető el.
Ha páros számú golyó van az asztalon, akkor 3 vagy 4 golyó vehető el.
Ha egy lépés negatív golyószámot eredményezne, akkor az nem léphető meg.
Ha valaki nem tud már lépni, akkor veszít, és ellenfele nyer.
Írj pszeudokódot, mely kiszámítja, hogy (optimális játékot feltételezve) a kezdő játékos nyerni vagy veszíteni fog!