From: James Edward Gray II <james@...>
Date: 2004-12-14T00:49:24+09:00
Subject: Re: [QUIZ] Learning Tic-Tac-Toe (#11)

On Dec 13, 2004, at 8:27 AM, Thomas Leitner wrote:

> | 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???

I'm not able to see an obvious flaw in your logic, but I did want to 
compliment you on your interface.  When I saw it I though, "How did 
Thomas know to write to my Tic-Tac-Toe library?"  I'll post it below so 
you can see how similar it is.  :D

James Edward Gray II

#!/usr/bin/env ruby

module TicTacToe
	module SquaresContainer
		def []( index ) @squares[index] end

		def blanks()	@squares.find_all { |s| s == " " }.size end
		def os()		@squares.find_all { |s| s == "O" }.size end
		def xs()		@squares.find_all { |s| s == "X" }.size end
	end
	
	class Board
		class Row
			def initialize( squares, names )
				@squares	= squares
				@names		= names
			end
			
			include SquaresContainer
			
			def to_board_name( index ) Board.index_to_name(@names[index]) end
		end
		
		def self.name_to_index( name )
			x = name.gsub!(/([a-cA-C])/, "").to_i - 1
			y = ($1.downcase)[0] - ?a
			x + y * 3
		end
		
		def self.index_to_name( index )
			if index >= 6
				"c" + (index - 5).to_s
			elsif index >= 3
				"b" + (index - 2).to_s
			else
				"a" + (index + 1).to_s
			end
		end
		
		def initialize( squares )
			@squares = squares
		end
			
		include SquaresContainer
		
		def []( *indices )
			if indices.size == 2
				super indices[0] + indices[1] * 3
			elsif indices[0].is_a? Fixnum
				super indices[0]
			else
				super Board.name_to_index(indices[0].to_s)
			end
		end
		
		def each_row
			rows = [ [0, 1, 2], [3, 4, 5], [6, 7, 8],
					 [0, 3, 6], [1, 4, 7], [2, 5, 8],
					 [0, 4, 8], [2, 4, 6] ]
			rows.each do |e|
				yield Row.new(@squares.values_at(*e), e)
			end
		end
		
		def moves
			moves = [ ]
			@squares.each_with_index do |s, i|
				moves << Board.index_to_name(i) if s == " "
			end
			moves
		end
		
		def won?
			each_row do |row|
				return "X" if row.xs == 3
				return "O" if row.os == 3
			end
			return " " if blanks == 0
			
			false
		end
		
		def to_s
			@squares.join
		end
	end
	
	class Player
		def initialize( pieces )
			@pieces = pieces
		end
		
		attr_reader :pieces
		
		def move( board )
			raise NotImplementedError, "Player subclasses must define move()."
		end
		
		def finish( final_board )  end
	end
	
	class HumanPlayer < Player
		def move( board )
			draw_board board
			
			moves = board.moves
			print "Your move?  (format: b3)  "
			move = gets
			move.chomp!
			until moves.include?(move.downcase)
				print "Invalid move.  Try again.  "
				move = gets
				move.chomp!
			end
			move
		end
		
		def finish( final_board )
			draw_board final_board
			
			if final_board.won? == @pieces
				print "Congratulations, you win.\n\n"
			elsif final_board.won? == " "
				print "Tie game.\n\n"
			else
				print "You lost Tic-Tac-Toe?!\n\n"
			end
		end
		
		private
		
		def draw_board( board )
			rows = [ [0, 1, 2], [3, 4, 5], [6, 7, 8] ]
			names = %w{a b c}
			puts
			print(rows.map do |r|
				names.shift + "  " + r.map { |e| board[e] }.join(" | ") + "\n"
			end.join("  ---+---+---\n"))
			print "   1   2   3\n\n"
		end
	end
	
	class DumbPlayer < Player
		def move( board )
			moves = board.moves
			moves[rand(moves.size)]
		end
	end
	
	class SmartPlayer < Player
		def move( board )
			moves = board.moves
			board.each_row do |row|
				if row.blanks == 1 and (row.xs == 2 or row.os == 2)
					(0..2).each do |e|
						return row.to_board_name(e) if row[e] == " "
					end
				end
			end

			if board[0] != @pieces and board[0] != " " and board[8] == " "
				return "c3"
			elsif board[8] != @pieces and board[8] != " " and board[0] == " "
				return "a1"
			elsif board[2] != @pieces and board[2] != " " and board[6] == " "
				return "c1"
			elsif board[6] != @pieces and board[6] != " " and board[2] == " "
				return "a3"
			end

			return "b2" if moves.include? "b2"
			
			return "a1" if moves.include? "a1"
			return "a3" if moves.include? "a3"
			return "c1" if moves.include? "c1"
			return "c3" if moves.include? "c3"
			
			moves[rand(moves.size)]
		end
	end
	
	class Game
		def initialize( player1, player2 )
			if rand(2) == 1
				@x_player = player1.new("X")
				@o_player = player2.new("O")
			else
				@x_player = player2.new("X")
				@o_player = player1.new("O")
			end
			
			@board = Board.new([" "] * 9)
		end
		
		attr_reader :x_player, :o_player
		
		def play
			until @board.won?
				update_board @x_player.move(@board), @x_player.pieces
				break if @board.won?
				
				update_board @o_player.move(@board), @o_player.pieces
			end
			
			if @o_player.is_a? HumanPlayer
				@o_player.finish @board
				@x_player.finish @board
			else
				@x_player.finish @board
				@o_player.finish @board
			end
		end
		
		private
		
		def update_board( move, piece )
			m = Board.name_to_index(move)
			@board = Board.new((0..8).map { |i| i == m ? piece : @board[i] })
		end
	end
end

if __FILE__ == $0
	if ARGV.size > 0 and ARGV[0] == "-d"
		ARGV.shift
		game = TicTacToe::Game.new TicTacToe::HumanPlayer,
								   TicTacToe::DumbPlayer
	else
		game = TicTacToe::Game.new TicTacToe::HumanPlayer,
								   TicTacToe::SmartPlayer
	end
	game.play
end