Minesweeper

Interesantna tema za samostalni rad, koja može da se pretoči u maturski rad je bot za minesweeper.

Klasičan Minesweeper možete naći na https://minesweeper.online/

Igra se na tabli mxn, na kojoj su sakrivene mine. Igrač treba da pronađe i označi sva polja na kojima se nalaze mine. Polja su inicijalno zatvorena. Igrač u jednom potezu otvara jedno polje. Ako se na polju nalazi mina igra se završava gubitkom. Ako se na polju ne nalazi mina igrač dobija informaciju koliko mina ima u susednim poljima, tj. na polju se prikazuje broj. Na osnovu te informacije igrač može da zaključi gde se nalaze mine, označi ta polja, otvori sva ostala i dokaže da je pronašao sva polja na kojima su mine. Broj sakrivenih mina je unapred poznat.

Uzmimo za primer mapu 3x3 na kojoj su neka polja već otvorena. Dva polja, gore levo i dole desno, nisu otvorena. Na mapi se nalazi jedna mina. U kom polju? U ovakvoj situaciji igrač će zaključiti da se mina nalazi u donjem desnom polju, jer samo tako brojevi u otvorenim poljima imaju smisla.

Agent

Agent donosi odluke na osnovu trenutne baze znanja i izvođenju zaključaka pomoću pravila na osnovu trenutnog znanja.

Jedan način da modelujemo znanje o igri je da svako polje predstavimo kao jednu varijablu/parametar koja će imati vrednost TAČNO ako se na tom polju nalazi mina, odnosno NETAČNO ako se ne nalazi mina.

Koje informacije o igri ima agent, šta opaža senzorima? Agent zna da li je otvoreno polje sa ili bez mine, i ako je polje bez mine zna koliko ima mina oko tog polja. Pogledajmo sledeći slučaj, gde je polje u sredini otvoreno, a susedna polja nisu. Susedna polja označena su slovima A,B,C…,H. Inače bismo koristili koordinate matrice, pa bi ovo bilo npr. Mapa[0,0], Mapa[0,1], …

Znamo da je jedno od susednih polja minirano ali ne znamo koje. Ako se na polju A nalazi mina parametar A će biti TRUE, itd. Logički iskaz kojim možemo opisati trenutno stanje je:

A+B+C+D+E+F+G+H    ili drugačije zapisano:  Or(A,B,C,D,E,F,G,H)   

Ovaj iskaz je sigurno tačan jer jedan od njih je tačan.

Zapravo znamo više od toga. U ovako napisanom iskazu iskaz će biti tačan i ako ih ima nekoliko koji su tačni, zbor prirode operatora OR. Agent zna da je tačno jedan od A,B,C,D,E,F,G,H tačan a ostali nisu, pa možemo da formulišemo precizniji iskaz:

Or(    And(A, Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),    And(Not(A), B, Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),    And(Not(A), Not(B), C, Not(D), Not(E), Not(F), Not(G), Not(H)),    And(Not(A), Not(B), Not(C), D, Not(E), Not(F), Not(G), Not(H)),    And(Not(A), Not(B), Not(C), Not(D), E, Not(F), Not(G), Not(H)),    And(Not(A), Not(B), Not(C), Not(D), Not(E), F, Not(G), Not(H)),    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), G, Not(H)),    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), H))

Ovaj iskaz je u DNF. Ako bismo ga zapisali u indeksnom obliku to bi bilo:

DNF(A,B,C,D,E,F,G,H) = Σ(1,2,4,8,18,32,64,128)

Prilično veliki broj kombinacija, i prilično velika formula. Stvar se dodatno komplikuje kada je na polju broj 2, gde imamo 8*7=56 klauza u DNF, broj 3 gde imamo 8*7*6=336 klauza itd.

Za mapu 8x8 ovo postaje realno veliki problem da se predstavi i sračuna.

Možemo da predstavimo znanje na drugačiji način: ako znamo da se u okolini ovog polja nalazi tačno jedan koji je miniran, imamo skup od osam polja od kojih se na tačno jednom nalazi mina:

set1=count1                      {A,B,C,D,E,F,G,H} = 1

Sada možemo da razmatramo neke specifične slučajeve koji nam mogu dalje dati korake algoritma (u stilu DPLL):

• Ako za neko polje znamo da na njemu nije mina, možemo da ga uklonimo iz skupova u kojima se pojavljuje, pri čemu count tih skupova ostaje isti:
  • x=FALSE and x in set1 ->   set1 = set1\x
• Ako za neko polje odredimo da je minirano, možemo da ga uklonimo iz svih skupova u kojima se pojavljuje i da smanjimo count tih skupova za 1, jer smo sigurni da je to jedno polje minirano:
  • x=TRUE and x in set1 ->   set1=set1\x, count1=count1-1
• Ako u nekom skupu imamo onoliko polja koliki je broj mina u tom skupu, onda je svako polje minirano:
  • set1==count1 ->   sva polja u set1=TRUE
• Ako je jedan skup podskup drugog skupa, onda možemo da taj drugi skup podelimo na dva dela, i da odredimo count za oba dela:
  • set1 subsetof set2 ->    set3 = set2\set1,  count3=count2-count1
• Ako za neko polje izvedemo da je minirano označićemo ga kao minirano
  • x=TRUE ->    M = M + x                (dodajemo polje u skup miniranih)
• Ako za neko polje odredimo da nije minirano označićemo ga kao neminirano
  • x=FALSE ->    N = N + x
• Ako skup miniranih ima očekivan broj mina možemo izvršiti proveru-otvaranje svih ostalih polja
• Ako skup neminiranih ima ukupno-broj mina možemo označiti ostala polja kao minirana (i proglasiti kraj-proveriti sva ostala polja).
• Ako u skupu neminiranih polja postoji neko polje koje nije otvoreno otvorićemo ga
• Ako su sva polja označena kao neminirana otvorena, otvorićemo nasumično polje koje se ne nalazi ni u jednom skupu. Ako nema takvog polja, otvorićemo neko nasumično polje. Ovde postoji prostor za optimizaciju verovatnoće (bolje je otvoriti polje koje je 1 od 7 nego polje koje je 2 od 3).

Svaku činjenicu (polje jeste-nije otvoreno, polje jeste-nije minirano, polje jeste-nije bezbedno) možemo da predstavimo kao polje u matrici dimenzija istih kao tabla. Nepoznata vrednost bi bila null. Za svaku vrstu činjenica (otvoreno, minirano, slobodno) bismo imali zasebnu matricu. Skupove predstavljamo tipom Skup, i čuvamo niz skupova koji ažuriramo operacijama.

Ovo je jedan način kako možemo da izgradimo algoritam. Potrebno je formirati konzistentan skup pravila, opisati ih kao logičke iskaze i implementirati funkciju koja će prolaziti kroz trenutno stanje „sveta“, vršiti izvođenje novih zaključaka (koja su polja sigurna a koja sumnjiva) i na osnovu toga birati akciju-koje se polje otvara.

https://cs50.harvard.edu/extension/ai/2020/spring/projects/1/minesweeper/