AlegsaOnline.com

Teoria combinatorie a jocurilor

Autor: Leandro Alegsa

11-10-2021

Teoria combinatorie a jocurilor, cunoscută și sub numele de CGT, este o ramură a matematicii aplicate și a informaticii teoretice care studiază jocurile combinatorii, fiind diferită de teoria jocurilor "tradiționale" sau "economice". CGT a apărut în legătură cu teoria jocurilor imparțiale, în special cu jocul Nim cu doi jucători, punând accentul pe "rezolvarea" anumitor tipuri de jocuri combinatorii.

Un joc trebuie să îndeplinească mai multe condiții pentru a fi un joc combinatoriu. Acestea sunt:

Jocul trebuie să aibă cel puțin doi jucători.
Jocul trebuie să fie secvențial (de exemplu, jucătorii alternează rândurile.)
Jocul trebuie să aibă informații perfecte (adică nicio informație nu este ascunsă, ca în poker).
Jocul trebuie să fie determinist (adică fără șansă). Norocul nu face parte din joc.
Jocul trebuie să aibă un număr definit de mutări posibile.
Jocul trebuie să se încheie în cele din urmă.
Jocul trebuie să se încheie atunci când unul dintre jucători nu mai poate să se miște.

Teoria combinatorie a jocurilor se limitează în mare măsură la studiul unui subset de jocuri combinatorii cu doi jucători, finite și care au un câștigător și un învins (adică nu se termină cu remize).

Aceste jocuri combinatorii pot fi reprezentate prin arbori, fiecare vârf al cărora reprezintă jocul care rezultă dintr-o anumită mutare din jocul aflat direct sub el în arbore. Acestor jocuri li se pot atribui valori de joc. Găsirea acestor valori de joc prezintă un mare interes pentru teoreticienii CG, la fel ca și conceptul teoretic de adăugare de jocuri. Suma a două jocuri este jocul în care fiecare jucător, la rândul său, trebuie să mute doar într-unul dintre cele două jocuri, lăsându-l pe celălalt așa cum era.

Elwyn Berlekamp, John Conway și Richard Guy sunt fondatorii acestei teorii. Aceștia au lucrat împreună în anii 1960. Lucrarea lor publicată s-a numit Winning Ways for Your Mathematical Plays (Modalități câștigătoare pentru jocurile matematice).

Definiții

În teorie, există doi jucători numiți stânga și dreapta. Un joc este ceva care permite stânga și dreapta să facă mutări în alte jocuri. De exemplu, în jocul de șah, există o configurație de pornire obișnuită. Cu toate acestea, ne putem gândi, de asemenea, la un joc de șah după prima mutare ca la un joc diferit, cu o configurație diferită. Așadar, fiecare poziție se numește, de asemenea, un joc.

Jocurile au notația {L|R}. L {\displaystyle L} $L$ sunt jocurile în care jucătorul din stânga poate să se mute. R {\displaystyle R} $R$ sunt jocurile în care se poate deplasa jucătorul din dreapta. Dacă cunoașteți notația șahului, atunci configurația obișnuită a șahului este jocul

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Punctele "..." înseamnă că există mai multe mișcări, așa că nu sunt afișate toate.

Șahul este foarte complex. Este mai bine să vă gândiți la jocuri mai ușoare. Nim, de exemplu, este mult mai simplu de gândit. Nim se joacă în felul următor:

Există zero sau mai multe teancuri de fise.
În timpul unui tur, un jucător poate să ia oricâte fise dorește dintr-un teanc.
Jucătorul care nu poate face o mutare pierde.

Cel mai simplu joc de Nim începe fără niciun fel de fise! În acest caz, niciun jucător nu se poate mișca. Acest lucru este indicat prin {|}. Ambele părți sunt goale, deoarece niciun jucător nu se poate mișca. Primul jucător care pleacă nu se poate mișca și, prin urmare, va pierde. În CGT, oamenii scriu adesea {|} ca simbolul 0 (zero).

Următorul joc, cel mai simplu, are o singură grămadă, cu un singur pion. Dacă jucătorul din stânga începe primul, acesta trebuie să ia pionul, lăsând dreptul fără nicio mișcare ({|} sau 0). În schimb, dacă dreapta mută prima, stânga nu va mai avea nicio mutare. Astfel, atât stânga cât și dreapta pot face o mutare la 0. Aceasta este reprezentată prin {{|}|{|}}}, sau {0|0}. Primul jucător care mută va câștiga. Jocurile egale cu {0|0} sunt foarte importante. Acestea sunt scrise cu simbolul * (stea).

Întrebări și răspunsuri

Î: Ce este teoria jocurilor combinatorii?

R: Teoria combinatorie a jocurilor (CGT) este o ramură a matematicii aplicate și a informaticii teoretice care studiază jocurile combinatorii și este diferită de teoria jocurilor "tradiționale" sau "economice".

Î: Ce condiții trebuie să îndeplinească un joc pentru a fi considerat un joc combinatoriu?

R: Pentru ca un joc să fie considerat un joc combinatorial, trebuie să aibă cel puțin doi jucători, să fie secvențial (adică jucătorii alternează rândurile), să aibă informații perfecte (adică nicio informație nu este ascunsă), să fie determinist (adică să nu fie o întâmplare), norocul nu poate face parte din joc, trebuie să existe un număr definit de mutări posibile, jocul trebuie să se încheie în cele din urmă, iar jocul trebuie să se încheie atunci când unul dintre jucători nu mai poate face nicio mutare.

Î: Pe ce tip de jocuri se concentrează teoria combinatorie a jocurilor?

R: Teoria combinatorie a jocurilor se concentrează în mare parte pe jocurile finite cu doi jucători care au învingători și învinși (adică nu se termină cu remize).

Î: Cum sunt reprezentate aceste tipuri de jocuri?

R: Aceste tipuri de jocuri pot fi reprezentate prin arbori, fiecare vertex reprezentând jocul rezultat dintr-o anumită mutare de la cea aflată direct sub el în arbore.

Î: Care sunt câteva obiective pentru teoreticienii CG?

R: Printre obiectivele teoreticienilor CG se numără găsirea de valori pentru aceste tipuri de jocuri, precum și înțelegerea conceptului de "adăugare de jocuri", care presupune ca fiecare jucător să facă o singură mutare în două jocuri diferite, lăsându-l pe celălalt neschimbat în timpul turei sale.

Î: Cine a fondat CGT?

R: Elwyn Berlekamp, John Conway și Richard Guy sunt creditați cu fondarea CGT în lucrarea lor publicată în anii 1960, intitulată Winning Ways for Your Mathematical Plays (Căi câștigătoare pentru jocurile tale matematice).