From: Thomas Leitner <t_leitner@...>
Date: 2004-12-13T23:27:19+09:00
Subject: Re: [QUIZ] Learning Tic-Tac-Toe (#11)

| This week's Ruby Quiz is to implement an AI for playing Tic-Tac-Toe,
| with a catch:  You're not allowed to embed any knowledge of the game
| into your creation beyond how to make legal moves and recognizing that
| it has won or lost.
| 
| Your program is expected to "learn" from the games it plays, until it
| masters the game and can play flawlessly.

So, I have also tried to program a learning AI player. However, it still
does not do what it should and I do not know why. Maybe someone with
more brains can help???

Here is the code for the AI player:

class AIPlayer < Player

  def initialize( game, sign )
    super( game, sign )
    @stats = {}
    @cur_stats = []
  end

  def move
    unless @stats.has_key? @game.board
      @stats[@game.board.dup] = {}
      @game.board.valid_moves.each {|m| @stats[@game.board][m] = 0}
    end
    moves = @stats[@game.board].sort {|a,b| a[1] <=> b[1]}
    result = moves.shift
    result = moves.shift while (moves.length > 0) && rand < 0.02
    @cur_stats << [@game.board.dup, result[0]]
    return result[0]
  end

  def game_finished( result )
    mult = case result
           when :won then 1000
           when :lost then -100
           else 0
           end
    @cur_stats.each_with_index do |o,i|
      @stats[o[0]][o[1]] += mult * 2**i
    end
    @cur_stats = []
  end

end

A short description for the code:

The @game object is the current game and knows the current board. When
it is the AI players move, the #move method is called and the AI player
has to return a number between 0 and 8. Thats because my tictactoe board
is a simple array and the array inidices correspond to these fields:

0 1 2
3 4 5
6 7 8

In the #move method, I create a new entry in the @stats Hash (key is the
board) if it does not have the current board as key and initialize its
value with a Hash (keys are the valid fields and values are set to 0).
After that the Hash with the valid moves for this board is taken from
the @stats Hash and sorted so that the moves with the highest
probability are in front. Then the first, or if rand < 0.02 the second
or if rand < 0.0.2 the third, ... value is returned.

If the game has finished, the #game_finished method is called and the
moves that were chosen in the game are assigned new values depending on
the result of the game.

-- 
|\  Thomas Leitner  --  thomas [underscore] leitner [at] gmx [dot] at
|>
|/  "Life is what happens to you while you're busy making other plans"