Kushdo që ka luajtur tik-tac-toe me siguri ka kuptuar se loja mund të barazohet gjithmonë, me kusht që asnjëri nga lojtarët të mos gabojë. Në të vërtetë, është e thjeshtë të krijosh një algoritëm që garanton një fitore ose barazim pavarësisht nga lëvizjet e bëra nga kundërshtari.
Ky është një shembull i parëndësishëm i një loje që është “zgjidhur” – një në të cilën rezultati përcaktohet që në fillim. Ka shumë të tjera që gjithashtu janë zgjidhur, por shumë që nuk janë zgjidhur.
Për teoricienët e lojërave dhe shkencëtarët e kompjuterave, vështirësia në zgjidhjen e një loje në përgjithësi varet nga numri i pozicioneve të mundshme. Për shembull, loja Connect 4 në një rrjet 6×7 ka 4,531,985,219,092 pozicione të mundshme. Shkencëtarët kompjuterikë e zgjidhën këtë në 1988 duke treguar se lojtari që shkon i pari mund të detyrojë gjithmonë një fitore.
Miliard Bilion
Damë (ose Draughts) është dukshëm më komplekse, me 500 miliardë miliardë pozicione të mundshme në bord. Kjo nuk u zgjidh deri në vitin 2007 kur shkencëtarët kompjuterikë treguan se nëse të dyja palët luajnë në mënyrë perfekte, loja është gjithmonë e barazuar.
Tani Hiroki Takizawa, një bioinformatik në Preferred Networks, një kompani kompjuterike në Japoni, ka zgjidhur Othello (ose Reversi), një lojë me 10 në fuqinë e 28 pozicioneve. “Zgjidhja e Othello-s, përcaktimi i rezultatit të një loje pa asnjë gabim të bërë nga asnjëri nga lojtarët, ka qenë prej kohësh një sfidë e madhe në shkencën kompjuterike,” thotë Takizawa, duke vazhduar të shpallë: “Othello tani është zgjidhur”.
Othello është një lojë tavoline me 2 persona e luajtur në një rrjet 8×8 që u shpik në Angli në 1883. Loja u bë e njohur në Japoni, SHBA dhe vende të tjera në vitet 1970 me Kampionatin Botëror që zhvillohej çdo vit që nga viti 1977 (përveç gjatë pandemia COVID-19).
Lojtarët vendosin në mënyrë alternative numëruesit në tabelë me anën e zezë ose të bardhë të kthyer nga lart. Veçantia e lojës aktivizon aftësinë për të kthyer numëruesit e zinj në të bardhë (dhe anasjelltas) kur përshtatet nga numërues të ngjyrës së kundërt. Kjo rrokullisje e bën veçanërisht të vështirë për lojtarët njerëzorë që të shikojnë përpara, prandaj dhe vështirësia e lojës.
Algoritmet kompjuterike nuk kanë probleme të tilla, natyrisht, dhe kanë mundur rregullisht lojtarët njerëzorë që nga vitet 1990. Tani Takizawa ka modifikuar një nga këto algoritme, një program të quajtur Edax, për të zgjidhur lojën me forcë brutale.
Dy faktorë e kanë bërë të mundur këtë. Takizawa modifikoi Edax për ta bërë atë më të përshtatshëm për këtë lloj zgjidhjeje të problemeve Othello dhe më pas e ndau detyrën në pjesë më të menaxhueshme. Ai e shikoi problemin pasi ishin zënë 14 hapësira me 50 hapësira boshe të mbetura në tabelë. Më pas ai shikoi përsëri kur kishin mbetur vetëm 36 hapësira boshe.
Më pas ai drejtoi programin e tij në një grup superkompjuterash të quajtur MN-J, në pronësi të Preferred Networks. Ky grup përfshin MN-3, aktualisht renditet superkompjuteri i 11-të më i fuqishëm në botë për sa i përket efikasitetit të energjisë (në vitin 2020 u rendit në vendin e parë).
Forcë e madhe
Rezultati është një provë brutale e forcës se loja e përsosur nga të dy lojtarët çon në një barazim.
Kjo hedh themelet për një program kompjuterik që luan gjithmonë lojën e përsosur. “Rezultati i Othello-s është një arritje monumentale për njerëzimin,” thotë Takizawa, ndoshta paksa i mashtruar.
Ka probleme të mundshme me provat e Takizawa. Matematikanët kanë shprehur prej kohësh shqetësime se nuk mund të mbështetet në provat kompjuterike sepse nuk ka asnjë mënyrë për të ditur nëse mund të ketë ndodhur një gabim kompjuterik.
Takizawa e pranon këtë. “Natyrisht, gabimet llogaritëse për shkak të defekteve të CPU ose kujtesës nuk mund të përjashtohen plotësisht,” pranon ai. “Sidoqoftë, pasi shumica dërrmuese e llogaritjeve u ekzekutuan në një grup kompjuteri me memorie të kontrollit dhe korrigjimit të gabimeve, ne besojmë se rezultatet janë pothuajse të padiskutueshme.”
Pra, çfarë ndodh më pas për shkencëtarët kompjuterikë që luajnë lojëra? Takizawa spekulon se shahu mund të jetë loja e radhës që do të zgjidhet si një sfidë madhështore. Megjithatë, kjo do të kërkojë shumë më shumë punë. Numri i pozicioneve të lojës në shah është befasues 10 në fuqinë 43.
Takizawa mendon se madhësia e madhe e kësaj hapësire kërkimi do të thotë se zgjidhja e saj do të kërkojë përparime teorike si dhe forcë brutale llogaritëse.
Nëse keni pak kohë të lirë – dhe akses në një superkompjuter rezervë – pse të mos e provoni!
Ref: Othello është zgjidhur: arxiv.org/abs/2310.19387
