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
···
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.
