... Un Scrabble izrādījās PSPACE-Complete

Scrabble, kas tika izgudrots ASV 20. gadsimta vidū, tagad ir pieejams desmitiem valodu un tiek pārdots simtos miljonu. Tas padara to par vienu no populārākajām spēlēm pasaulē.

Tas, protams, ir izraisījis spēļu teorētiķu interesi. Tā kā Scrabble ir tik veiksmīga spēle, kļūst dabisks jautājums, lai noteiktu optimālas spēles atrašanas skaitļošanas sarežģītību, saka Maikls Lampis no KTH Karaliskās Tehnoloģiju institūta Zviedrijā un daži draugi.

Tas pats jautājums ir veiksmīgi uzdots par daudzām galda spēlēm, piemēram, šahu, Go un Othello, kuras parasti ir PSPACE vai EXPTIME-pabeigtas. Bet Scrabble ir sarežģītāks, jo spēlētāji nezina, kādā secībā tiks izvilktas flīzes, kas nozīmē, ka iespējai ir lielāka loma.

Jautājums, uz kuru Lampis un viņa kolēģi cenšas atbildēt, ir šāds: cik grūti ir noteikt labāko spēles stratēģiju, ņemot vērā Scrabble pozīciju?

Viņi norāda, ka jebkurā konkrētā kārtā Scrabble spēlētājs saskaras ar diviem uzdevumiem: izlemt, kuru vārdu veidot, un izlemt, kur to novietot uz tāfeles. Šie uzdevumi ir saistīti, jo veidojamie vārdi ir atkarīgi no burtu novietojuma uz tāfeles.

Bet kurš no šiem uzdevumiem apgrūtina Scrabble? Lampis un līdzgaitnieki parāda, ka abi ir smagi un sniedz pierādījumus, lai pamatotu savu apgalvojumu. Tas ir iespaidīgi, jo ļauj mums “redzēt”, kāpēc Scrabble ir grūts.

Mēs konstatējam, ka spēles gaitā Scrabble spēlētājiem ir jāveic nevis viens, bet divi skaitļošanas ziņā grūti uzdevumi, kas, iespējams, ir iemesls, kāpēc Scrabble ir tik jautri spēlēt, viņi raksta.

Tas nenozīmē, ka skaitļošanas sarežģītības teorētiķi ir pabeiguši un saputināti ar Scrabble. Viņu nākamais uzdevums ir noskaidrot, vai ir polinoma laika algoritms, lai noteiktu kustību, kas maksimāli palielinātu šajā kārtā sasniegto rezultātu.

Tagad tas būtu noderīgi!

Atsauce: arxiv.org/abs/1201.5298 : Scrabble ir PSPACE-Complete

paslēpties