Dilema del Prisionero Iterado (Resultados)

Tras describir el Dilema del Prisionero Iterado y retaros a que me enviáseis vuestros algoritmos he estado unos días jugueteando con el código y viendo como se enfrentaban.

Hoy toca repasar los resultados

Los algoritmos

He recibido un total de 11 algoritmos diferentes. Algunos han sido propuestos por más de una persona. Me limitaré a dar una breve explicación de qué hace cada uno de ellos:

  • 0) Donde las dan las toman: Se trata de un algoritmo que en la primera jugada coopera y en las siguientes hace exactamente lo que haya hecho el adversario en la jugada anterior.
  • 1) Judas: Este se limita a traicionar siempre
  • 2) Job: Y este simplemente coopera siempre
  • 3) Donde las dan las toman + empezamos bien: Igual que 0) pero traicionando en la primera jugada
  • 4) Donde las dan las toman no determinista: En la primera jugada colabora y en las siguientes realiza, al azar, una de las jugadas que haya realizado el contrario a lo largo del enfrentamiento.
  • 5) Donde las dan dos veces las toman: En las dos primeras rondas colabora y luego traiciona si y solo si el contrario le ha traicionado en las últimas dos jugadas.
  • 6) Estudiando al enemigo: Realiza la secuencia (Colabora, Colabora, Colabora Traiciona, Colabora, Traiciona, Traiciona, Traiciona, Colabora, Colabora, Colabora) y en lo que queda de enfrentamiento usa la información obtenida de las reacciones del contrario para decidir que hacer.
  • 7) Donde las dan las toman + reconocedor de hermanos: Si el contrario tiene la misma población que él y no lo ha atacado en ningún momento… entonces debe ser un hermano suyo y por lo tanto colabora siempre. En el caso contrario juega “Donde las dan las toman”
  • 8) Judas + reconocedor de hermanos: Igual que el anterior, pero en vez de jugar “Donde las dan las toman” con los que no son sus hermanos juega “Judas”
  • 9) Donde las dan las toman de media: Empieza colaborando en la primera jugada y luego colabora o traiciona aleatoriamente de manera proporcional a la cantidad de veces que ha colaborado el contrario en las últimas 10 jugadas.
  • 10) Donde las dan 2 de cada 3 veces las toman: Un algoritmo que traiciona sólo cuando el contrario lo ha traicionado 2 veces en las últimas 3 jugadas.

Resultados

Los siguientes gráficos muestran una competición entre los 11 algoritmos. La competición duraba 60 generaciones y en cada generación todos los algoritmos se enfrentaban entre sí en batallas de 500 rondas.

La cantidad de individuos que obtenía cada algoritmo en la siguiente generación se calculaba de la siguiente manera: En total nacían 20 individuos y morían otros tantos. Los algoritmos que habían obtenido una puntuación por encima de la media se repartían los 20 nacimientos de manera proporcional a los puntos por encima de la media que habían obtenido. De manera similar, los algoritmos que estaban por debajo de la media se repartían las defunciones. En la primera generación todos los algoritmos empezaban con 100 representantes.

Así pues, un algoritmo puede pasar de crecer a menguar cada vez que muere uno de los adversarios ya sea porque ese adversario se le daba especialmente bien y ya no lucha con él o ya sea porque entonces, aún obteniendo una puntuación similar a la generación anterior, queda por debajo de la media de los restantes algoritmos.

Dilema del Prisionero Iterado

Lo primero que puede observarse es que el temido Donde las dan las toman gana de calle empatando con el Donde las dan las toman con reconocedor de hermanos que, a efectos prácticos, se comportó exactamente igual que su mucho más sencillo pariente.

Por otra parte Judas y su variante sofisticada Judas con reconocedor de hermanos son los primeros en caerse de la competición. Podemos concluir que en este caso saber si te enfrentabas a uno de tus hermanos no fue de mucha ayuda.

Donde las dan las toman de media fue el siguiente en dejar el juego. Es probable que esto sea debido a que era demasiado tolerante con los demás algoritmos.

Donde las dan dos veces las toman y Donde las dan las toman con empezamos bien murieron casi a la vez. Es muy significativo que este último tan sólo se diferencia, a priori, en la primera jugada respecto a Donde las dan las toman, y sin embargo, sus resultados son mucho peores.

Dilema del Prisionero Iterado - Top 5

Entre los 5 mejores algoritmos se encuentra Donde las dan dos de cada 3 veces las toman que, por lo visto también era demasiado permisivo.

Prácticamente empatados entre sí están Estudiando el enemigo y (Oh sorpresa!) Job. Esto es realmente divertido ya que son el algoritmo más complejo y el más sencillo respectivamente.

Finalmente, y en un meritorio 2º puesto de la general, no encontramos a Donde las dan las toman no determinista. Un algoritmo en el que, sinceramente, tenía depositadas todas mis esperanzas. A priori es superior a Donde las dan las toman ya que es no determinista y eso imposibilita un ataque a medida contra él.

Conclusiones

Si ahora mismo tuviese que elegir un algoritmo que pueda desbancar en un futuro a Donde las dan las toman elegiría la siguiente variante de Donde las dan las toman no determinista: En la primera jugada colabora y en las siguientes realiza, al azar, una acción que haya realizado el contrario antes. Eso sí, en vez de escoger de manera uniforme entre todas las acciones que ha realizado el contrario escoge con más probabilidad las más recientes. Por ejemplo, realiza al última acción del contrario con probabilidad 1/2, la penúltima con probabilidad 1/4, la antepenúltima con probabilidad 1/8, etc…

Una mejora de Estudiando al enemigo basada en la Inferencia Bayesiana puede dar buenos resultados en competiciones a muchas rondas ya que, no sólo sería capaz de responder y adaptarse a lo que haga el enemigo sino que también sería capaz de explotar al enemigo siendo un poco agresivo siempre que esto sea rentable.

Por cierto, ¿Alguien sabe como se llaman las secuencias de dígitos de longitud mínima que contienen todas las posibles secuencias de una longitud dada?.

Trabajando en binario un ejemplo para longitud 3 sería: 0001011100 ya que contiene todas las posibles secuencias de tres dígitos (000, 001, 010, 011, 100, 101, 110, 111) y es de longitud mínima.

Estoy seguro de que, dadas las posibles aplicaciones de estas secuencias tienen que estar bien estudiadas y tener nombre pero no he conseguido encontrarlo.

Efectivamente tenían nombre: Secuencias de De Bruijn (Gracias Javi!)

En fin, si tengo tiempo estudiaré estas dos vías y ya publicaré los resultados. ¿Alguna otra idea?

BOLAEXTRA: El código (Python) que he usado para calcular todo esto me ha quedado bastante feo. Si, aún así alguien quiere usarlo para algo que deje un comentario y se lo enviaré por e-mail.

Escrito en 18/09/09 10:05 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

¡Muy buen análisis! Yo que vos, haría un concurso más, pero prohibiendo todos estos algoritmos, a ver con qué sale la gente… :)

marcos | 18/09/09 13:16 | #
Gravatar.com se ha roto

Para el donde las dan las toman no determinista no seria mejor empezar traicionando? Un saludo! muy interesantes los resultados

OuFeRRaT | 18/09/09 13:49 | #
Gravatar.com se ha roto

@Marcos: Creo que las competiciones de algoritmos será mejor dejarlas a los profesionales del tema ;-)

@OuFeRRaT: Es probable que de esa manera pueda “encender la chispa” y obligar a otros algoritmos a hacer algo más que colaborar indefinidamente. Aún así dudo que su puntuación mejore.

Carlos Luna | 18/09/09 13:57 | #
Gravatar.com se ha roto

Jeje, m’ha agradat molt avui… és interessant :)

Meldor | 18/09/09 15:23 | #
Gravatar.com se ha roto

El protocolo P2P Bittorrent, que se basa en el dilema del prisionero iterado, utiliza precisamente el algoritmo del ojo por ojo (“tit for tat”) como implementación oficial y recomendada.

maeghith | 20/09/09 04:53 | #
Gravatar.com se ha roto

@maeghith: Moooola! Había oído hablar de ciertas aplicaciones de la Teoría de Juegos al mundo de las telecomunicaciones (como por ejemplo usar los índices de Banzhaf o de Shapley-Shubik para decidir quien merece más ancho de banda) pero no conocía esta.

Merci por tu aportación!

Carlos Luna | 20/09/09 11:58 | #
Gravatar.com se ha roto

Me gustaría saber algo más sobre qué lenguaje has usado y cómo has realizado el experimento, si no te importa. Tengo en mente un par de proyectos y me vendría bien saber cómo has procedido.

Te sigo.

Un saludo.

Antonio | 23/09/09 12:34 | #
Gravatar.com se ha roto

Muy interesante. No conocía esto del enfrentamiento de algoritmos hasta hace unas semanas. Me interesa mucho el código en python del que hablas en especial la mejora al algoritmo de “estudiando al enemigo”, la que incluye la inferencia bayesiana. Trabajo con un pequeño juego que tiene que ver con un fractal y me pregunto si podrías mandar a mi correo tu código en python. Me gustaría implementar algunas ideas.
Muchos saludos!

Luis Torres | 25/04/10 23:04 | #
Gravatar.com se ha roto

@Antonio & @Luis Torres: Me sabe mal, pero he estado buscando el scrypy de Python que usé en su día para hacer la competición y no he sido capaz de encontrarlo. Si os puedo ayudar de alguna otra forma estaré encantado de hacerlo!

Carlos Luna | 27/04/10 22:26 | #
Gravatar.com se ha roto

Hola, quisiera que me pasaras el código, por favor

Andreina | 16/06/10 03:31 | #
Gravatar.com se ha roto

@Andreina: Hola, quisiera que leyeras mi comentario anterior, por favor

Carlos Luna | 16/06/10 09:34 | #
Gravatar.com se ha roto

Buen día, me interesaría ver el código Python si aún lo tienes. Una consulta, para la obtención de puntos, supongamos que tengo 3 algoritmos con 10 individuos.
algo1
algo2
algo3.

Por cada generación cada individuo del algo1 debería batallar contra todos los individuos del algo2 y del algo3, los del 2 contra todos los del 3 y así sucesivamente?
los individuos de un mismo algoritmo no batallan entre sí?

Saludos.

Jose | 16/06/16 15:14 | #
Gravatar.com se ha roto

hola como va??? tenes el codigo??? muy bueno el apunte, necesito el codigo para un tp q s m vence este jueves, gracias

Oscar | 19/12/16 01:44 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)