Note de curs, probleme algoritmică, 22 noiembrie 2013

În acest curs am discutat probleme simple de teoria jocurilor:

• 1180 - Stone Game;
• 1087 - The Time to Take Stones;
• 1282 - Game Tree.

Stările jocului

Toate problemele au stările jocului foarte bine (clar) definite. În plus, jocurile sunt aciclice: printr-o succesiune de mutări nu se poate reveni în aceeași stare a jocului.

Pentru cel puțin una din stările jocurilor se știe rezultatul jocului (câștigă jucătorul aflat la mutare, pierde jucătorul aflat la mutare sau jucătorii fac remiză).

Pentru restul stărilor jocului se calculează (printr-o formulă recurentă) rezultatul jocului dacă cei doi jucători urmează o strategie optimă.

Formula recurentă

Formula recurentă este următoarea:

• dacă dintr-o stare jucătorul aflat la mutare poate muta (ajunge) numai în stări câștigătoare (pentru adversarul lui, care îi va urma la mutare) atunci starea respectivă este pierzătoare;
• dacă dintr-o stare jucătorul aflat la mutare poate muta (ajunge) în cel puțin o stare pierzătoare (pentru adversarul lui, care îi va urma la mutare) atunci starea respectivă este câștigătoare - iar strategia optimă cere jucătorului să mute în starea pierzătoare identificată;

Formula recurentă este puțin mai complicată (dar similară) dacă pot exista și stări de remiză.