admin
Administrator
Data inscrierii: 30/Ian/2007
Mesaje: 76
|
 Trimis: 08/02/2007 15:09 Titlul subiectului: Jocul NIM |
 |
|
Jocul NIM
=========
Doua persoane A si B au la dispozitie n gramezi (stive)
de obiecte (monede/pietre/chibrite) si joaca impreuna un joc.
Fiecare poate lua dintr-o singura gramada oricate obiecte
(in limita numarului de obiecte din gramada).
Castiga cel care ia ultimul obiect, adversarul sau
nemaiputand muta.
Analiza jocului
===============
Acest joc este cel mai important tip al jocurilor dintre
doi parteneri.
Origine: Numele jocului a fost dat de matematicianul
american Charles L. Bouton, derivat dintr-un vechi
cuvant englez, cu semnificatia "a lua"; oricum versiunea
moderna a jocului NIM seamana cu un vechi joc chinezesc
numit Tsianshidzi (sau "ridicarea pietrelor").
Numim stare a jocului vectorul v=(v1,v2,...,vn) reprezantand
numarul de obiecte din fiecare gramada. Pentru fiecare stare
se poate determina daca duce la castigul (C) sau pierderea (P)
jocului de catre jucatorul aflat la mutare.
Teorema
=======
O C-stare a jocului este data de valoarea pozitiva a sumei xor:
S=v[1] xor v[2] xor...xor v[n]
Evidet, S=0 => P-stare (pierderea jocului)
S:=0;
for i:=1 to n do
S:=S xor v[i]
Strategia de castig
===============
Presupunem ca jucatorul A muta primul. Avem doua situatii:
1) dispoziția initiala a jocului este o dispoziție de castig,
adica are o suma Sxor >0. In acest caz strategia jucatorului
A este de a face o mutare care sa duca la obtinerea unei
P-stari (de pierdere) pentru jucatorul B.
Se determina numarul x de obiecte pe care le poate lua A
din ecuatia: S xor v[i]=v[i] - x, ceea ce duce la o stare
cu suma xor nula pentru B. De aici rezulta:
=> x=v[i] - S xor v[i]
Deci trebuie sa determinam o gramada pentru care valoarea
lui x este strict pozitiva.
for i:=1 to n do
if v[i]>S xor v[i] then
begin
x:=v[i]-S xor v[i];
break
end
2) Daca jucatorul A se afla initial intr-o P-stare
(de pierdere) va muta astfel incat sa pastreze aceasta
situatie, asteptand ca B sa faca o mutare gresita (desi
o strategie buna a lui B face imposibil ca el sa piarda).
Cautam aceeasi valoare a lui x ca si la cazul 1.
Tabela operatiei xor (NIM)
==========================
0 | 1 | 2 | 3 | 4 | 5 |
-----------------------
1 | 0 3 2 5 4
2 | 3 0 1 6 7
3 | 2 1 0 7 6
4 | 5 6 7 0 1
5 | 4 7 6 1 0
Cateva precizari
================
- Jocuri impartiale : sunt jocuri in care ambii jucatori
au aceleasi mutari posibile.
- Orice joc impartial poate fi redus la jocul NIM - rezultat
datorat matematicienilor R.P. Sprague si P.M. Grundy
- La jocul NIM nu este posibila remiza!
Variante
========
1. NIM modificat: aceleasi mutari, pierde cel care ia ultimul obiect.
2. cautare pe google <a href="http://www.google.ro/search?hl=ro&q=NIM+game&btnG=C%C4%83utare+Google&meta="><img src="http://www.google.com/favicon.ico"></a> |
|
