Degtukų žaidimas

Taškai: 12

Benas su draugu žaidžia degtukų žaidimą. Eilėje yra 13 degtukų. Žaidėjai paeiliui ima 1, 2 arba 3 degtukus. Laimi tas, kuris paima paskutinįjį degtuką. 
 
Užuomina: kai lieka 4 degtukai, Benas negali laimėti. Jis turi išvengti tokios situacijos.
Benas pradeda žaidimą. Kiek degtukų jis turi paimti, kad laimėtų?
A.    Vieną degtuką
B.    Du degtukus
C.    Tris degtukus
D.    Nesvarbu, kiek imti, vis tiek laimės

Paaiškinimas

Tai klasikinis žaidimas dviem su alternatyviais ėjimais. Po kiekvieno ėjimo kompiuteris analizuoja skirtingus galimus ėjimus ir skaičiuoja didžiausią tikimybę laimėti. Tada kompiuteris vykdo savo ėjimus ir analizuoja vėl.
Šis žaidimas yra tiksliojo algoritmo pavyzdys. Kitiems žaidimams, kurie neturi tiksliojo algoritmo sprendimo, ar kai tikslusis algoritmas veikia lėtai, taikomi euristiniai metodai. Euristinis metodas – uždavinių sprendimo metodas, kai randamas priimtinas, bet nebūtinai tikslus (optimalus) uždavinio sprendinys. 1997 m. pirmą kartą istorijoje pasaulio šachmatų čempionate kompiuteris įveikė žmogų naudodamas euristiką.

Reikšminiai žodžiai: tikslusis algoritmas, sprendimo medis.

Atsakymas

Atsakymas: vieną degtuką.
Benas pirmiausia ima vieną degtuką. Lieka 12 degtukų. Kitais ėjimais Benas ima degtukus taip, kad likusių degtukų skaičius dalytųsi iš 4. Laikantis šios strategijos jo draugas darys paskutinį ėjimą, turėdamas 4 degtukus, ir Benas laimės žaidimą.

 

 
Informacija atnaujinta 2016-10-18 10:55:36