Teoria jocurilor

(Categoria Teoria jocurilor, Autor Filip Cristian Buruiana)

• Capitole
• Notiuni de baza
• Jocul NIM
• Numere Sprague-Grundy
• Adunarea jocurilor
• w-numere
• Aplicatii si probleme

Notiuni de baza

Prin joc se intelege un sir de decizii (actiuni, mutari), luate de parti ale caror interese se ciocnesc. Jocurile studiate in acest articol sunt cele care au doi parteneri. De asemenea, toate jocurile analizate sunt jocuri cu mutari libere: la fiecare pas, jucatorul aflat la mutare poate alege sa efectueze una in mod constient, in functie de regulament si de situatia jocului la momentul respectiv. Decizia nu este constransa de niciun factor aleator, precum zaruri, carti de joc sau monede.
Se spune ca un jucator are strategie sigura de castig daca acesta va castiga, indifierent de modul in care ar incerca adversarul sa ii impiedice victoria. Daca un joc respecta toate cele cinci conditii de mai jos si unul dintre jucatori alege intotdeauna strategia cea mai buna, atunci rezultatul este predeterminat:

• Se termina dupa un numar finit de pasi
• Nu contine un element intamplator introdus de zaruri, carti de joc, etc.
• Este un joc cu informatie completa, in care un jucator inainte de a executa o mutare cunoaste rezultatele tuturor mutarilor precedente
• Un jucator poate vedea toate mutarile adversarului
• Jucatorii muta alternativ