From: James Edward Gray II <james@...>
Date: 2004-12-13T11:59:35+09:00
Subject: Re: [QUIZ] Learning Tic-Tac-Toe (#11)

On Dec 10, 2004, at 8:29 AM, Ruby Quiz 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.

Okay, I think I have a working solution.  My problem is in another 
area.  My thinking about Tic-Tac-Toe itself seems flawed.

First, I decided to generate all the positions and came up with:

#!/usr/bin/env ruby

$seen = [ ]

def generate( board, piece, &pos_handler )
	(0..8).each do |i|
		next unless board[i, 1] == " "
		pos = board.dup
		pos[i] = piece

		next if $seen.include?(pos)
		$seen << pos
		pos_handler.call(pos)
		
		next if pos.split("").values_at(0..2)		== [piece] * 3 or
				pos.split("").values_at(3..5)		== [piece] * 3 or
				pos.split("").values_at(6..8)		== [piece] * 3 or
				pos.split("").values_at(0, 3, 6)	== [piece] * 3 or
				pos.split("").values_at(1, 4, 7)	== [piece] * 3 or
				pos.split("").values_at(2, 5, 8)	== [piece] * 3 or
				pos.split("").values_at(0, 4, 8)	== [piece] * 3 or
				pos.split("").values_at(2, 4, 6)	== [piece] * 3
		
		generate(pos, (["X", "O"] - [piece])[0], &pos_handler)
	end
end

puts "1\n   \n   \n   \n\n"
count = 1
generate(" " * 9, "X") do |pos|
	count += 1
	puts "#{count}\n#{pos[0..2]}\n#{pos[3..5]}\n#{pos[6..8]}\n\n"
end

__END__

Does the 5478 positions I'm getting from that sound right?

Then I tried to brainstorm transforms which yield equivalent positions. 
  Obviously rotating 90, 180, or 270 are some.  I also use "mirror" 
(swap first and third columns), and mirror with 90, 180, and 270 
rotates.

That gets me down to:

#!/usr/bin/env ruby

class Position
	def self.rotate( pos )
		pos.split("").values_at(6, 3, 0, 7, 4, 1, 8, 5, 2).join
	end
	
	def self.mirror( pos )
		pos.split("").values_at(2, 1, 0, 5, 4, 3, 8, 7, 6).join
	end

	def initialize( pos )
		@pos = pos
	end
	
	def ==( pos )
		return true if @pos == pos
		
		transform = pos
		3.times do
			transform = Position.rotate(transform)
			return true if @pos == transform
		end

		transform = Position.mirror(pos)
		return true if @pos == transform
		3.times do
			transform = Position.rotate(transform)
			return true if @pos == transform
		end
		
		false
	end
	
	def to_s; "#{@pos[0..2]}\n#{@pos[3..5]}\n#{@pos[6..8]}\n" end
	def inspect; @pos end
end

$seen = [ ]

def generate( board, piece, &pos_handler )
	(0..8).each do |i|
		next unless board[i, 1] == " "
		pos = board.dup
		pos[i] = piece

		next if $seen.include?(pos)
		$seen << Position.new(pos)
		pos_handler.call($seen[-1])
		
		next if pos.split("").values_at(0..2)		== [piece] * 3 or
				pos.split("").values_at(3..5)		== [piece] * 3 or
				pos.split("").values_at(6..8)		== [piece] * 3 or
				pos.split("").values_at(0, 3, 6)	== [piece] * 3 or
				pos.split("").values_at(1, 4, 7)	== [piece] * 3 or
				pos.split("").values_at(2, 5, 8)	== [piece] * 3 or
				pos.split("").values_at(0, 4, 8)	== [piece] * 3 or
				pos.split("").values_at(2, 4, 6)	== [piece] * 3
		
		generate(pos, (["X", "O"] - [piece])[0], &pos_handler)
	end
end

puts "1\n   \n   \n   \n\n"
count = 1
generate(" " * 9, "X") do |pos|
	count += 1
	puts "#{count}\n#{pos}\n"
end

__END__

That gives me 765 positions, which I know is wrong, but I can't find 
the error in my logic...

James Edward Gray II