Teoría de xogos (VII): O xogo do cempés

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 7 de outubro de 2010 Teoría de juegos VII – Juego del ciempiés, de Javier “J” Sedano, que pode lerse en El Cedazo. Toda a serie Teoría de juegos está publicada en forma de libro, dispoñible aquí.]

[O artigo previo da serie é Teoría de xogos (VI): Contar (II).]

Neste capítulo da serie presentamos un xogo introducido por primeira vez por Robert W. Rosenthal: o xogo do cempés.

TRUST 1210K POWERC@M OPTICAL ZOOM
Malia ser un bicho, é un dos máis entrañables. Alguén non tentou algunha vez atopar un para lle contar as patas? [Fonte: Image*After]
As regras do xogo son as seguintes:

  • Dous xogadores, Ana e mais Alberte, que, amais de xogaren con espellos, raios láser e pelotas ultrarrápidas, tamén se dedican aos cempés no lecer.
  • Comeza con dous montóns de moedas de 1 €. No primeiro montón hai 2 moedas e, no segundo, 0 moedas (si, son montóns pequeniños, xa medrarán). Ambos os dous ponse diante de Ana.
  • En cada quenda, o xogador ten dúas opcións:
    1. Pode quedar co montón grande e darlle o pequeno ao outro xogador.
    2. Ou pode darlle ambos os montóns ao outro xogador e que comece outra quenda.
  • Cada vez que un xogador escolle a opción 2, os montóns medran: unha moeda en cada montón.
  • Se o xogo acada as 100 roldas e ninguén decidiu nunca a opción 1, o xogo remata e ninguén gana nada.

Unha pausa duns minutos para pensares o que farías ti se foses un dos xogadores.

.

.

.

Forma extensiva do xogo

Este é un xogo que non pode representarse mediante unha matriz de pagamentos. O mellor xeito de representar este xogo é a forma extensiva.

Forma extensiva ou forma en árbore: é unha árbore onde cada nó é unha decisión que debe tomar un xogador. Os fillos de cada nó son as posibles decisións, que poden ser unha folla cun array de recompensas (un elemento por cada xogador) ou outro nó de decisión.

 

Non todos os xogos poden representarse axeitadamente mediante a matriz de pagamentos: algúns é mellor representalos coa forma extensiva. Para aclarar a definición, vexamos o exemplo do noso xogo do cempés.

j_juegos_arbol1

En cada nó representamos, cunha icona, se quen toma a decisión é Ana ou Alberte. Nunha árbore máis formal ou con máis xogadores, adoita indicarse cun círculo e un número indicando o número do xogador, pero aquí gustáronme máis os bonequiños de cores. Nótese que, neste xogo, Ana e Alberte vanse alternando, pero noutros xogos podería ser que o mesmo xogador deba tomar máis dunha decisión (se ben a miúdo iso pode agruparse nunha sorte de «nó de multidecisión», se realmente son decisións consecutivas sen nada entremedias).

Para axudar neste xogo, xunta cada nó anotamos o estado dos montóns de moedas.

As saídas de cada nó son o número da decisión que toman (ver máis arriba: 1 é repartir, 2 é darlle os montóns ao outro). Neste xogo é unha decisión binaria, pero noutros xogos podería haber máis de dúas decisións posibles.

As follas son un array onde amosamos primeiro a recompensa para Ana e, seguidamente, a recompensa para Alberte. Se houbese máis xogadores, teriamos un elemento por xogador.

Deste xeito, se as decisións fosen 2-2-1 (Ana pasa, Alberte pasa, Ana reparte), a recompensa sería 4, 2 (Ana recibe 4 € e Alberte 2 €).

Esta forma extensiva é moi apropiada para representarmos xogos deterministas e complexos como, por exemplo, o xadrez. Existen xeitos teóricos de, dada a árbore completa, calcular cal é a mellor decisión. De feito, isto é o que tentan facer os xogadores artificiais de xadrez: calculan toda a árbore de todas as posibles decisións (miñas e do opoñente) a partir da situación actual e logo atopan o mellor movemento (veremos máis verbo disto en vindeiros artigos). Dicimos «tentan» porque a complexidade computacional de tal cálculo está moi por diante do dispoñible hoxe en día, de maneira que os xogadores artificiais existentes empregan algoritmos heurísticos (dicimos que un algoritmo é heurístico cando non podemos demostrar que é óptimo, pero semella que é bo dabondo) para poderen podar ramas completas da árbore e reducila a un problema abordable. Hoxe en día semella que a calidade dun xogador artificial de xadrez se define basicamente consonte a calidade dos seus heurísticos.

Por que chamamos a isto xogo do cempés? Porque podemos facer o debuxo doutro xeito (nótese que é o mesmo de antes, simplemente recolocándoo):

j_juegos_arbol2

Se debuxásemos as 100 quendas do xogo, semellaría un cempés con 100 patas. De feito, na meirande parte da literatura con relación a este xogo, debúxano directamente así. Nós preferimos amosar ambos os debuxos para que servise tamén como exemplo xenérico que ilustrase a forma extensiva.

Tradicionalmente chámaselles xogo do cempés a todos os xogos que seguen esta estrutura… aínda que non teñan 100 quendas.

Resultado teórico

O resultado teórico óptimo pode atoparse mediante indución. Máis adiante na serie veremos que estamos a aplicar unha estratexia maximin e formalizarémola. Polo de pronto, fagámolo dun xeito máis ou menos intuitivo.

Supoñamos que chegamos á quenda 100. Os montóns teñen 101 e 99 moedas respectivamente. Nesa quenda tocaríalle xogar a Alberte. Se Alberte decide 2, os montóns desaparecen, así que Alberte debe irremediablemente decidir 1. Dese xeito, Ana quedaría con 99 € e Alberte quedaría con 101 €.

Pero claro, antes da quenda 100 debe xogarse a quenda 99, na cal é Ana quen decide. Na quenda 99 os montóns teñen 100 e 98 moedas respectivamente. Se Ana decidir 1, obterá 100 € (e Alberte, polo tanto, obterá 98 €). Pola contra, se decidir 2, chegará a quenda 100… pero Ana xa sabe o que fará Alberte na quenda 100, e sabe que ela recibirá 99 €. Recapitulemos: pode decidir 1 (e quedar con 100 €) ou decidir 2 (e quedar con 99 €). Así que nunca decidirá 2, senón que decidirá 1, quedando co montón meirande.

Pero claro, antes da quenda 99 debe xogarse a quenda 98, na cal é Alberte quen decide. Na quenda 98 os montóns teñen 99 e 97 moedas respectivamente. Se Alberte decidir 1, obterá 99 € (e Ana obterá 97 €). Pola contra, se decidir 2, chegará a quenda 99… pero Alberte xa sabe o que fará Ana na quenda 99, e sabe que el recibirá 98 €. Así que nunca decidirá 2, senón que decidirá 1, quedando co montón meirande.

Pero claro, antes…

E así chegamos ata a quenda 1, onde Ana sempre debe escoller 1, quedando con 2 €.

Resultado empírico

Pois non, non coincide moito. Cando se repite este xogo obsérvase que raramente o primeiro xogador decide repartir na primeira quenda. Non soamente iso, senón que o outro xogador tampouco adoita repartir na segunda quenda. E así sucesivamente. Dependerá de moitos factores ata onde cheguen: a cantidade inicial nos montóns, a diferenza entre o montón grande e o pequeno, a cantidade e forma en que se incrementan, a cantidade máxima de quendas, o número de xogadores… pero, xeralmente, menos do 10 % dos xogadores decide repartir na primeira quenda (e soamente pasan dese 10 % cando a recompensa inicial é moi alta).

Buscáronse explicacións para este resultado empírico contraditorio co resultado teórico, pero non as imos ver neste artigo, senón noutros posteriores onde se verán aínda máis claras. Tamén veremos en vindeiros artigos unha situación real (e perigosa) que pode estudarse mediante este xogo. Pero antes, dedicaremos outros artigos a máis dous ou tres conceptos.

Para que vaias abrindo boca e non creas que non o imos tratar: se o resultado teórico e o empírico non coinciden, pode ser por dúas cousas. Pode ser porque o resultado empírico estea mal (que o experimento estea mal deseñado, que esteamos a medir outra cousa sen sabelo, que as condicións de fronteira non estean ben…) ou ben porque a teoría estea mal (que non teña en conta todo o que debe, que as condicións de fronteira das que parte non se poidan reproducir, que as premisas fosen falsas…). Veremos que pode haber un pouco de cada.

[O seguinte artigo da serie é Teoría de xogos (VIII): Dous terzos da media (I).]


Este artigo e mais a súa tradución están publicados baixo licenza CC BY-NC-ND 2.5 ES.

Advertisements

Deixar unha resposta

introduce os teu datos ou preme nunha das iconas:

Logotipo de WordPress.com

Estás a comentar desde a túa conta de WordPress.com. Sair / Cambiar )

Twitter picture

Estás a comentar desde a túa conta de Twitter. Sair / Cambiar )

Facebook photo

Estás a comentar desde a túa conta de Facebook. Sair / Cambiar )

Google+ photo

Estás a comentar desde a túa conta de Google+. Sair / Cambiar )

Conectando a %s