2. Juegos

La mayoría de los juegos de mesa y una gran cantidad de problemas informáticos pueden resolverse mediante una adecuada modelización en estados y aplicar un algoritmo de búsqueda entre estos estados.

Para acotar el problema, pensemos en un juego de tablero de 2 jugadores, por ejemplo, las tres en raya, las damas, el ajedrez, el othello, etc. ¿Cómo podría programarse un juego de este tipo?:

Bien, en primer lugar, un tablero es una estructura de datos de tipo matriz donde cada elemento puede ser ocupado por el jugador 1, ocupado por el jugador 2, ó vacio (en juegos como el ajedrez donde cada jugador tiene diferentes fichas habría que completar el enfoque). Una partida es una secuencia de estados por los que pasa un tablero. Ahora veamos cómo debería actuar nuestro sistema inteligente para ganarnos en una partida.

Para ilustrar la implementación de estos enfoques recomiendo instalar el paquete tictactoe que implementa las 3 en raya con 2 niveles de dificultad easy (implementa reglas tontas) y hard (implementa minimax). Dejo el código de las funciones clave al lector:

Ejemplo 1. Extracto de código de tictactoe


  # implements a simple win/block/random-move AI
  def move_ai_easy
    if (m = blockWin) >= 0
      @gamefield.field[m] = 2
    else
      # set random point
      while true
	x = rand(3)
	y = rand(3)
	if @gamefield.get(x,y) == 0
	  @gamefield.set(x,y)
	  break
	end
      end
    end
    @nmoves += 1
  end

  # implements a more clever AI using the negamax tree search method
  def move_ai_hard
    best = -Inf
    besti = -1
    @gamefield.player = 1

    order = [4,0,2,6,8,1,3,5,7] # see text
    0.upto(8) do |ctr|
      i = order[ctr]
      if @gamefield.field[i] == 0
	@gamefield.field[i] = 2
	value = -@gamefield.negamax
	@gamefield.field[i] = 0
	if value > best
	  best = value
	  besti = i
	end
      end
      
      break if (@nmoves == 0) && (best == 0) # see text
    end
    
    @gamefield.player = 2
    @gamefield.field[besti] = 2

    @nmoves += 1
  end
      

De este modo, queda brevemente ilustrado el modo en que se pueden aplicar técnicas de Inteligencia Artificial en los juegos.