Skip to content

Rezolvarea şahului

18 March 2008

Până revin cu nişte posturi plictisitoare despre construirea compilatoarelor, mi-am amintit de o problemă interesantă despre care am discutat mai demult cu un prieten, anume rezolvarea jocului de şah. Construirea unui graf orientat cu nodurile reprezentând toate poziţiile care pot apărea pe tablă şi muchiile reprezentând mutările, se poate dezvolta un algoritm care să poată determina, încă de la prima mutare, un final avantajos al partidei (eu susţin că este remiză, prietenul cu care discutam susţine că albul va câştiga).

Dacă stăm să ne gândim la numărul de ramificaţii posibile la fiecare mutare, problema pare NP-completă. Totuşi, în cazul şahului, spaţiul problemei este finit. Nu există un n care, dacă creşte, să crească şi timpul de soluţionare a problemei. Din câte am înţeles, există aproximativ 10^49 poziţii posibile, un număr extrem de mare dar un număr finit. Având suficient spaţiu de stocare şi suficientă putere de procesare, se poate determina o soluţie optimă pentru jocul de şah. Ce ar presupune asta? Ar fi practic imposibil ca un om să învingă un calculator la acest joc. Ştim că Deep Blue l-a bătut pe Kasparov, dar a fost un meci strâns, cu victorii câştigate atât de campion cât şi de computer. Dacă şahul s-ar rezolva, nici un om n-ar mai putea învinge, indiferent de capacitate, un calculator şi chiar şi o partidă jucată de două calculatoare s-ar termina cu o remiză.

Numărul 10^49 este un număr imens, într-adevăr, şi acesta ar fi doar numărul de noduri al grafului. Numărul de muchii (mutări posibile) ar fi şi mai mare, însă, dacă e să cred predicţiile pe care le-am tot auzit în ultima vreme – cum că peste vreo 10 ani un computer va avea puterea de procesare a creierului uman şi că peste 20 de ani un computer va avea puterea de procesare a întregii rase umane – atunci sunt convins că în timpul vieţii mele şahul va fi rezolvat.

Food for thought: şahul, “jocul regilor”, vechi de câteva secole, cu nenumărate cărţi scrise despre el, teorii, campioni şi campionate, redus la o succesiune predeterminată de mutări cu un final cunoscut de la început de un algoritm de căutare exhaustivă (adică brute force, nimic fancy). Eu zic că în maxim 30 de ani. Aşa că mai jucaţi acum, cât timp mai este distractiv🙂

From → tech

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: