23 de maig de 2021

Juguem a "Parell guanya"

"Jugarem a guanyar i a perdre alhora
i farem festa"
Màrius Sampere 

A l'any 80 el meu amic Carles Vallès (l'altra pota del Calaix abans de l'aparició d'internet) i jo érem alumnes de'n Jordi Deulofeu i ens va proposar fer un treball sobre jocs d'estratègia. Eren els primer anys que ell mateix els estudiava. Va ser el meu primer contacte amb un tema que, des de aleshores, no he deixat mai de banda. Ell ens va posar en contacte amb una altra "ànima inquieta", en Jordi Achón, amb el que vam poder fer pràctiques amb alumnat de la 2a etapa de l'antic EGB. Aquest ens va deixar un llibre: "Algoritmos y computadoras" de B.A. Trakhtenbrot on hi apareixia el joc objecte d'aquest article. Crec que no l'he vist mai més citat en cap altre lloc.

És un joc de regles molt senzilles i d'anàlisis ric, però no massa directe. De fet, en el seu moment, no el vam estudiar massa perquè el cas concret que comentava el llibre tenia una estratègia que no ens va semblar "descobrible" per l'alumnat (ni per nosaltres mateixos que, tot just, fèiem les primeres passes en l'estudi de jocs). Això sí, el vam utilitzar per mostrar com fer diagrames en arbre per a la cerca d'estratègies guanyadores. El joc que es proposava tenia el nom de "Parell guanya" i les regles eren les següents:

  • Hi ha 27 fitxes a la taula.
  • Cada jugador/a, en el seu torn, pot agafar una, dues, tres o quatre fitxes.
  • Guanya qui al final, quan no queden més fitxes a la taula, té una quantitat parell.
Us proposem que proveu de fer algunes partides amb aquest applet.


Com es veu és un joc en el què no poden haver taules i tots dos tenen, en tot moment, tota la informació de les fitxes que queden i de les que té cadascun. Per altra banda, el joc té una quantitat limitada de jugades (entre 7 i 27). Tampoc depèn de l'atzar ni de l'habilitat física. Tot això implica que hi ha d'haver una estratègia guanyadora per a un dels jugadors. I que si en una jugada un s'equivoca en l'aplicació de l'estratègia, aquesta passa a l'altre.

Per a investigar l'estratègia del joc farem diferents variants, podent agafar altres quantitats de fitxes, i utilitzarem diagrames en arbre, taules... I mirarem si podem trobar pautes generals d'estratègia o no.

Investiguem el joc?
En l'anàlisi de jocs és una bona tècnica reduir el joc modificant les regles convenientment. Per tant, podem començar estudiant que només es puguin agafar una o dues fitxes i per a diferents quantitats de fitxes inicials.

Agafem una o dues fitxes

Encara que sembli ridícul podem començar pensant què passarà si a la taula, inicialment, només hi ha una fitxa, si n'hi ha tres, si n'hi ha cinc... i anar recollint observacions.
  • Una fitxa inicial
Considerant el zero com a nombre parell, guanyarà el segon jugador (B), el que no comença
  • Tres fitxes inicials
En aquest cas guanyarà el primer jugador (A), agafant-ne dues. Obligatòriament B haurà d'agafar la que queda i quedar-se amb una quantitat senar.
  • Cinc fitxes inicials
En aquest cas potser ja ens convé fer un arbre del joc. Podem fer-lo complet, amb totes les partides possibles. Encara que, en general, no és el més aconsellable perquè es fan grans de seguida, ens pot ser útil per a familiaritzar-nos amb ells i amb el joc. Explicarem la llegenda: en verd les possibles jugades d'A, en blau les de B. Una anotació com 1 (3-2) significa que agafa una fitxa, queden 3 i ara en total en té 2 a la mà. Al final de cada camí està indicat qui ha guanyat (A o B).

Les línies vermelles mostren l'estratègia guanyadora per a B

Com es pot veure a la taula, per a cada possible jugada d'A hi ha una resposta concreta de B que li portarà a la victòria. A continuació mostrem un arbre reduït que recull només l'estratègia de B.


Com es veu és impossible que B, si no s'equivoca, perdi.
  • Set fitxes inicials
En aquest cas guanyarà A de la següent manera: agafa dues fitxes inicials i deixa cinc a la taula. A partir d'aquí aplicarà l'arbre de l'estratègia de 5 fitxes.
  • Nou fitxes inicials
Ara de nou ens toca fer un arbre. No cal que el fem complet ja que podem anar eliminant jugades clarament perdedores.  Si fem un esborrany i el depurem veurem que l'estratègia guanyadora serà, de nou, per a B.

  • Onze fitxes inicials
Guanya A agafant dues fitxes a la primera jugada i aplicant després l'arbre de nou.
  • Generalitzem?
Sembla que podem començar a definir algunes idees generals:
    • Si la quantitat inicial de fitxes és de la forma 4n+1 hi ha estratègia guanyadora per a B
    • Si la quantitat inicial és de la forma 4n+3 guanyarà A si comença agafant dues fitxes.
    • Un cop s'està en situació guanyadora només cal jugar igual que el contrari: si agafa una, n'agafarem una; si n'agafa dues també agafarem dues. L'única excepció és quan s'està obligat si a la taula només queda una fitxa.
    • Una altra manera de veure-ho és deixar sempre una quantitat senar a la taula (excepte a l'última jugada si es pot deixar la taula neta).
Servirà aquesta manera de jugar si variem la quantitat de fitxes a agafar?

Agafem una, dues o tres fitxes

Si voleu, abans de començar l'estudi podeu practicar amb aquest applet que et deixa triar la quantitat de fitxes incials.


Per a una i tres fitxes el joc el guanyen B i A, respectivament.

  • Cinc fitxes inicials
No és triga gaire a descobrir que l'estratègia és per a A si comença agafant una fitxa.



  • Set fitxes inicials
En serveix el mateix arbre anterior per a A, però agafant tres fitxes a la primera jugada.

  • Nou fitxes inicials
En aquest cas l'estratègia és per a B.



  • 11 fitxes inicials
Si A agafa 2 fitxes al principi pot jugar amb l'estratègia de l'arbre anterior

  • Abans de mirar 13 fitxes inicials... reflexionem
Sembla que tenim alguns indicis. Alguns entren en contradicció amb el cas de treure 1-2 fitxes. Si sortim d'una posició guanyadora per a B, per exemple, ara no funciona deixar senar sempre al contrari.  Tampoc fer la mateixa jugada que ell. Ara sembla que:
    • si agafa una hem d'agafar tres.
    • si agafa tres hem d'agafar una.
    • si agafa dues hem de mirar si queda a la taula un quantitat parell o senar. Si és senar agafarem tres i si és parell agafarem una.
De 13 no podem passar a deixar nou fitxes en una jugada directa. Podem pensar que si estem a quatre de distància i som segons sempre podem arribar segur (si agafa 1 agafarem 3, si agafa 2 nosaltres també 2 i, si agafa 1, nosaltres 3). Però això ens deixa amb una quantitat de fitxes a la mà senar o parell, cosa que segur influeix en el resultat final. Ho podem veure amb un exemple en el què si A agafa 3 i B respon amb una fitxa, tot i deixant 9, perdrà indefectiblement.


Hi ha la possibilitat de que 13 sigui, ben estudiada, una posició guanyadora per a B. Seria coherent ja que 13 és de la forma 4n+1 i amb 1-2 ho eren, però tenim que 5 també ho és i és guanyadora per a A. I, ja avancem que sortint amb una fitxa hi ha una estratègia per a A.

Encara un reflexió més. Hem dit abans que si un jugador té una estratègia guanyadora i s'equivoca en la seva aplicació automàticament aquesta passa a A. Però aquesta no té perquè ser exactament igual a la de l'arbre que teníem. Per exemple, si amb 11 fitxes inicials, en la que la sortida guanyadora per a A era agafar-ne dues a la primera jugada, si s'equivoca i agafa una, la resposta de B no ha de ser agafar-ne una també (la que falta per completar les dues que hauria d'haver agafat A) sinó que ha de ser agafar-ne 2 i deixar 8 a la taula.

Si a l'error d'A agafant 1 en comptes de 2, B respon agafant-ne 1, deixant-ne 9, A pot recuperar l'estratègia guanyadora.

A l'error d'A agafant-ne 1, B ha de respondre agafant-ne 2. Així recupera l'estratègia guanyadora

Com es veu, un cop recuperada l'estratègia es continua amb les mateixes normes de resposta al contrari (si n'agafa 1, nosaltres 3; si n'agafa 3, nosaltres 1; si n'agafa 2 hem de mirar si el que queda és parell, i n'agafem una, o si és senar, i n'agafem 3). Però costa saber quina és la primera resposta correcta. Hem de canviar la mirada en la investigació.


Replantegem la forma d'estudiar el joc: fem taules


Fer diagrames d'arbre pot ser una mica pesat. A més, hem vist que tampoc, si no tenim un arbre complet del joc, és difícil apropiar-se d'estratègies quan el contrari s'equivoca. Gran part del problema rau en que, a l'hora de triar la jugada, no només hem de tenir en compte les fitxes que queden, sinó que també s'han de considerar si tenim a la mà una quantitat parell o senar. Es poden donar quatre situacions:

    • Que quedi a la taula una quantitat parell i tinguem a la mà una parell (Pp)
    • Que quedi una quantitat parell i tinguem una senar (Ps)
    • Que quedi una quantitat senar i tinguem una parell (Sp)
    • Que quedi una quantitat senar i tinguem una senar (Ss)
Podem fer una taula que ens indiqui, per a cada situació, quina és la jugada guanyadora. I, si és una situació perdedora (guanyadora per a B) podem marcar la cel·la de color verd. De fet, una bona estratègia tractarà de portar al contrari a aquestes cel·les verdes perquè a partir d'aquí tindrem l'estratègia guanyadora. Construir la taula progressivament no és gaire difícil. Per exemple, si volem estudiar les respostes a la situació de 7 fitxes i tenim ja resoltes les jugades de 6, 5, 4 (que són les accessibles en una jugada) només es tracta de triar el moviment que porta a una casella verda.

Abans de fer la taula cal fer una observació: hi ha cel·les que no podem omplir. Si el nombre superior de la columna indica la quantitat de fitxes que queden a la taula, la P o la S de la fila que ens indiquen la seva paritat ha de ser congruents. A la columna del 5 no es donaran les situacions Pp i Ps. Pintarem aquestes caselles de gris.

 

1-2-3 1 2 3 4 5 6 7 8 9
Pp                  
Ps                  
Sp                  
Ss                  

 

Comencem amb una, dues, tres i quatre fitxes per a començar a a omplir la taula:

  • Si hi ha una fitxa a la taula i jo tinc a la mà una quantitat parell (1-Sp), perdré. Pintaré la casella de color verd
  • Si hi ha un fitxa a la taula i jo tinc una quantitat senar (1-Ss) guanyaré si l'agafo perquè passaré a tenir un total parell. 

1-2-3 1 2 3 4 5 6 7 8 9
Pp                  
Ps                  
Sp                  
Ss 1                

  • Si hi ha 2 fitxes a la taula i jo tinc una quantitat parell guanyaré si les agafo
  • Si tinc una quantitat senar guanyaré si només agafo una (jo tindré parell i l'altre es veurà obligat a quedar-se-la). Anirà a la casella 1-Sp i ja hem comentat abans que ens convé portar al contrari a les caselles verdes.  
123 1 2 3 4 5 6 7 8 9
Pp   2              
Ps   1              
Sp     2            
Ss 1   3            
  • Si hi ha 3 fitxes i tinc una quantitat parell, agafaré dues. Així l'altre agafarà l'última i quedarà amb un total senar. El porto a 1-Sp.
  • Si tinc una quantitat senar agafaré les 3. Deixaré la taula neta i em quedaré amb una quantitat parell.
  • Si hi ha 4 fitxes i tinc parell, estic perdut (4Pp). Si agafo 1 m'agafarà 3. Si n'agafo 2 agafarà una i hauré de quedar-me la que queda. Si n'agafo 3 em quedaré amb senar i l'altre, agafant la que queda, deixatà la taula neta. Pintarem la cel·la de verd
  • Si tinc senar i agafo 3 li deixo a la cel·la verda 1-Sp
1-2-3 1 2 3 4 5 6 7 8 9
Pp   2              
Ps   1   3          
Sp     2            
Ss 1   3            

  • Amb 5 fitxes, si tinc parell (5-Sp) hem vist abans, per l'arbre, que guanyaré si agafo cinc. Cal pensar que a la situació d'inici del joc no tenim cap fitxa, el que considerem parell.
  • I si tinc senar estic perdut. Si agafo una quedarà la situació 4 Pp que és perdedora. Si agafo 2 el contrari trobarà la situació 3-Sp i em guanyarà agafant-ne 2. I si agafo 3 el contrari trobarà 2-Pp, agafarà les dues que queden i guanyarà. 
1-2-3 1 2 3 4 5 6 7 8 9
Pp   2              
Ps   1   3          
Sp     2   1        
Ss 1   3            

Si ens hi fixem ara podem continuar mirant a quina casella anem a parar. El nostre objectiu és anar a les verdes. I hem d'estar atents a identificar bé a quina casella anem a parar perquè hem de canviar el punt de vista per veure què farà el contrari: per exemple, si jo m'he quedat 3-Sp per al contrari és 3-Ss. Continuant així podem completar la taula, per exemple fins a 17 fitxes.

123 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Pp   2       1   3   2       1   3  
Ps   1   3   2       1   3   2      
Sp     2   1   3       2   1   3    
Ss 1   3       2   1   3       2   1

Si mirem amb atenció cadascuna de les files de la taula hi trobarem uns cicles de 8 caselles. Sense tenir en compte les quatre grises de cada cicle, seran

    • Pp: 2-V-1-3
    • Ps: 1-3-2-V
    • Sp: V-2-1-3
    • Ss: 1-3-V-2
Això ens permet continuar ampliant la taula fins a la quantitat de fitxes que vulguem. També podem esbrinar el valor de cada fila jugant amb divisions i residus. Ho farem més tard. Ara el que proposarem serà una simplificació de la taula reduint-la a dues files. Podem veure que la situació Pp i Ss es corresponen a que el contrari tingui una quantitat de fitxes senar, ja que en tot dos casos la suma de les fitxes de la taula i les meves és parell. Complementàriament Ps i Sp impliquen que el contrari té una quantitat de fitxes parell. Per tant, podem reunir aquestes parelles de files i així, de pas, desapareixeran les cel·les grises. Ara cada fila indica si la quantitat de fitxes del contrari és senar o parell.

1-2-3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Senar 1 2 3     1 2 3 1 2 3     1 2 3 1
Parell   1 2 3 1 2 3     1 2 3 1 2 3    

 

Ara els cicles de vuit els podem definir més clarament:

    • Senar: 1-2-3-V-V-1-2-3
    • Parell: V-1-2-3-1-2-3-V
Ara podem definir una estratègia general per al joc quan es poden agafar una, dues o tres fitxes. O bé mirar a la taula quina jugada haig de fer (i jugar a l'atzar quan estic a una cel·la verda) o fer aquests càlculs.

    • Dividir la quantitat de fitxes entre vuit  i mirar el residu.
    • Si el contrari té una quantitat senar de fitxes, agafaré una fitxa si el residu és 1 o 6, dues si és 2 o 7, i tres si és 3 o 0. Si és 4 o 5 jugaré a l'atzar i esperaré que l'altre s'equivoqui en algun moment.
    • Si el contrari te una quantitat parell de fitxes, agafaré una fitxa si el residu de dividir per 8 és 2 o 5, agafaré dues si és 3 o 6, i agafaré tres si és 4 o 7. Si és 1 o 0 jugaré a l'atzar.


Mirem més taules


Ara us adjuntem les taules per a jocs amb 1-2 fitxes, d'una a quatre i d'una a cinc. També incloem la d'una a tres per poder trobar pautes posteriorment,

  • Taula per a 1-2 (els asteriscs indiquen quantitats inicials guanyadores per a B)

1-2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
S 1 2   1 1-2 2   1 1/2 2   1 1-2 2   1 1/2 2  
P   1 2   * 1 2   * 1 2   * 1 2   * 1 2


  • Taula per a 1-2-3. 
1-2-3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
S 1 2 3     1 2 3 1 2 3     1 2 3 1 2 3
P   1 2 3 1 2 3     1 2 3 1 2 3     1 2
  • Taula per a 1-2-3-4  (els nombres vermells indiquen jugades fora de patró)
1-2-3-4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
S 1 2 3 4   1 2 3 4 4   1 2 3 4 4   1 2
P   1 2 3 4   * 1 2 3 4   * 1 2 3 4   *

 

  • Taula per a 1-2-3-4-5 
1-2-3-4-5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
S 1 2 3 4 5     1 2 3 4 5 1 2 3 4 5    
P   1 2 3 4 5 1 2 3 4 5   1 2 3 4 5 1

 

Hi ha pautes generals?


És molt evident que a cada taula trobem cicles i regularitats en les jugades. Per descobrir-les és millor separar els jocs segons les opcions de tirada: si són d'ordre senar (d'1 a 3 o d'1 a 5) o d'ordre parell (1-2 o d'1 a 4). I, en tots dos casos analitzar primer la fila en la què el contrari té parell i, després, la que té senar. Per a cada cas mirarem com es generen els nombres de la fila, on van les caselles verdes i la llargada del cicle. Cal recordar que les caselles verdes són guanyadores per a qui deixa al contrari en elles i perdedores per a qui hi va a parar. És a dir, que el nostre objectiu serà sempre deixar a l'altre en una d'aquelles caselles.

  • Jugades possibles d'ordre senar (amb nombres d'1 a n on n és senar)
    • Fila parell. Comença amb una casella verda, s'escriuen dues sèries ordenades de les jugades possibles i es tanca amb una altra casella verda: V, 1, 2,, 3... n-1, n, 1, 2,, 3... n-1, n, V. 
    • Longitud del cicle: 2n+2.
    • Fila senar. Es fa un cicle ordenat de tirades, es posen dues caselles verdes, i es posa un altre cicle de tirades: 1, 2,, 3... n-1, n, V, V, 1, 2,, 3... n-1, n.
  • Jugades possible d'ordre parell (amb nombres d'1 a on n és parell)
    • Fila parell. Comença amb una casella verda, s'escriu una sèrie ordenada de jugades possibles i es tanca amb una altra casella verda: V, 1, 2,, 3... n-1, n, V.
    • Longitud del cicle: n+2
    • Fila senar. En aquest cas comencem el cicle més tard. Assenyalem en verd la casella anterior a tancar el cicle (si és de 6, la casella 5). Després escrivim el cicle de tirades possibles ordenadament i repetim la darrera jugada. És a dir, a partir de la columna n-1 fem: V, 1, 2,, 3... n-1, n, n. Les primeres caselles que ens havien quedat en blanc les omplim amb la sèrie de jugades possibles: 1, 2,, 3... n-1, n.
És evident que estem intentar generalitzar a partir de dos casos de cada tipus. Ara el que tocaria és construir un parell de taules més i comprovar-les. Us convidem a fer-ho.

Una petita conclusió

No hem trobat una estratègia general senzilla de descriure per a qualsevol partida possible segons les opcions de retirada de fitxes. En cada cas l'estratègia serà lleugerament diferent. Però hem vist algunes coses:
  • Hem de considerar si el joc és d'ordre senar o parell.
  • Per a decidir la jugada hem de mirar la quantitat de fitxes que queden per agafar i si el contrari té una quantitat parell o senar.
  • Podem fer taules de doble entrada amb la quantitat de fitxes que queden per agafar i indicant si el contrari té una quantitat parell o senar. A cada casella podem indicar la jugada a fer. També podem indicar que si estem allà "estem perduts".
  • Aquestes jugades fan cicles amb una llargada depenent de l'ordre parell o senar de les possibilitats de tria. Aquests cicles tenen pautes de formació i ens permeten deduir les tirades que corresponen a cada cas a partir dels residus de dividir la quantitat de fitxes que hi ha a la taula entre la llargada del cicle.
I a l'aula?
  • Jugar-hi. Al educació infantil o al cicle inicial de primària ens pot servir per a diferenciar parells de senars.
  • A CS de primària o al principi de l'ESO es pot estudiar alguna versió senzilla del joc, amb no masses fitxes (per exemple, 13) i amb poques opcions de tria (1-2 o 1-2-3). Per a poques fitxes es poden fer diagrames en arbre i marcar les estratègies. També podem proposar directament les taules per a omplir. En aquests cas haureu d'optar per si poseu les de quatre files o les reduïdes de dues. En tot cas, per a algunes situacions, sobre tot les que determinaran caselles verdes, convindrà fer arbres reduïts per veure si porten a caselles de la taula ja conegudes. 
  • D'aquestes versions es poden fer programes amb Scratch o Snap ajustats: per a una quantitat fixa de fitxes i determinant sempre qui comença, si la màquina o l'humà.
  • Amb els més grans es pot treballar un model de joc, per exemple 1-2-3 i després, per grups, treballar altres possibilitats (1-2, 1 a 4, etc.). A continuació, col·lectivament es poden buscar les pautes de les diferents taules i, si es vol, fer programes més sofisticats a partir de l'estudi dels residus.
  • I, a qualsevol edat, es poden explorar variants del joc: qui té parell perd, es poden agafar de 2 a 4 fitxes, etc.

Cap comentari:

Publica un comentari a l'entrada