Anar al contingut

Joc imparcial

De L'Enciclopèdia, la wikipedia en valencià

En la teoria de jocs combinatoris, un joc imparcial és un joc en el que els moviments permesos depenen només de la posició i no de quin dels dos jugadors té la tanda actualment, i a on els pagaments són simètrics. En atres paraules, l'única diferència entre el jugador 1 i el jugador 2 és que el jugador 1 va primer. El joc seguix fins que s'alcança una posició terminal. Una posició terminal és aquella des de la que no és possible realisar cap moviment. Llavors un dels jugadors és declarat guanyador i l'atre perdedor. Ademés, els jocs imparcials es juguen en informació perfecta i sense moviments aleatoris, lo que significa que tota l'informació sobre el joc i les operacions d'abdós jugadors és visible per a abdós jugadors.

Els jocs imparcials inclouen Nim, Brots, Kayles, Quarto, Cram, Chomp, Subtract a square, Notakto i els jocs poset. l'escacs i el go no són imparcials, ya que cada jugador solament pot colocar o moure peces del seu propi color. Els jocs com el pòquer, els daus o el va dominar no són jocs imparcials, ya que depenen de l'encert.

Els jocs imparcials poden ser analisats usant el teorema de Sprague-Grundy, afirmant que cada joc imparcial baix la convenció normal de joc és equivalent a un nimber. La representació d'este nimber pot canviar d'un joc a un atre, pero cada estat possible de qualsevol variació d'un tauler de joc imparcial deuria poder tindre algun valor nimber. Per eixemple, es poden calcular varis montons de Nim en el joc Nim, i despuix sumar-los usant la suma de nimber, per a donar un valor nimber per al joc.

Un joc que no és imparcial es diu joc partisano, encara que alguns jocs partisanos encara poden evaluar-se utilisant nimbers com Domineering.[1] Domineering no es classificaria com un joc imparcial, ya que els jugadors usen peces que actuen de manera diferent, un jugador en va dominar vertical, un atre en va dominar horisontal, trencant aixina la regla de que cada jugador deu poder actuar utilisant les mateixes operacions.

Requisits

Tots els jocs imparcials deuen complir les següents condicions:

  • Dos jugadors deuen alternar tandes fins que s'alcance un estat final.
  • S'elegix un guanyador quan un jugador ya no pot canviar de posició ni realisar cap operació.
  • Deu haver un número finit d'operacions i posicions per a abdós jugadors. Per eixemple, en Nim, els jugadors deuen llevar un subconjunt d'una pila que està actualment en joc. Com hi ha un número finit de monedes en qualsevol pila, un jugador solament pot traure un número finit de monedes.
  • Totes les operacions deuen poder ser realisades per abdós parts. En tots els jocs imparcials, els jugadors realisen accions en algun tauler de joc, ya siga en forma de piles per a Nim o files i columnes Cram. Abdós jugadors estan actuant en el tauler fins que el tauler ya no pot canviar d'alguna manera.
  • Cap acció en el joc pot dependre de l'encert. Qualsevol inclusió d'encert significaria que no hi ha informació perfecta sobre el joc, ademés, les accions no poden minimisar-se descartant qualsevol forma d'estratègia inductiva[2]

Referències

  1. ↑ (2015-12-24) Advances in computer games : 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers, Herik, Jaap van donen,, Plaat, Aske,, Kosters, Walter, Cham. OCLC 933627646. ISBN 978-3319279923.
  2. ↑ Ferguson, Thomas S. (Fall 2000). «Game Theory».

Bibliografia

En anglés:

  • (1982) Winning Ways for your Mathematical Plays (vol. 2 vols.), Academic Press.; Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (1982). vol. 1. ISBN 0-12-091101-9.; Berlekamp, Elwyn R. (1982). vol. 2. ISBN 0-12-091102-7.
  • (2001–2004) Winning Ways for your Mathematical Plays, 2nd edició (vol. 4 vols.), A K Peters Ltd.; Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2001-01-16). vol. 1. ISBN 1-56881-130-6.; vol. 2. ISBN 1-56881-142-X.; Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (2003-06-15). vol. 3. ISBN 1-56881-143-8.; Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (2004-06-15). vol. 4. ISBN 1-56881-144-6.