Now that's just cool! Thanks Hans.
James Edward Gray II
On Dec 11, 2004, at 1:12 PM, Hans Fugal wrote:
It would be good to be able to play against eachother when this is all over, so I propose the following 'protocol'. It's not complicated and probably not ready for tournament tic-tac-toe ;-), but it should do nicely.
Here comes my solution. As always I've set up a website where you can browse
everything online, that will be the most comfortable way.
Correction: The address is:
http://ruby.brian-schroeder.de/quiz/tictactoe/
On Mon, 13 Dec 2004 04:44:02 +0900 Brian Schröder <ruby@brian-schroeder.de> wrote:
[snip]
--
Brian Schröder
http://ruby.brian-schroeder.de/
I did. It's interesting b/c genetic agents are absolutely stupid and take a
long time to learn. Nonetheless I ran a population of 100 through a 5000
generations and they did improve, but still not perfect. I worry that it is
difficult to escape local maxima (which tells you something about Darwinian
evolution itself.)
As to the logic. I simply gave them a "tiny" abstract computer which gets
programmed with a simple AST. To do this I divide the board into three parts:
slots, and X's and O's postions. The slots are numbered as follows:
256 | 128 | 64
On Monday 13 December 2004 03:17 am, martinus wrote:
Has anyone tried a genetic programming approach? I have tried it, but
it does not work as expected. My problem is how to represent the logic
of the individuals so that mutation/crossover makes sense.martinus
-----+-----+----
32 | 16 | 8
-----+-----+----
4 | 2 | 1
X's and O's representation of the board are simply a binary number
cooresponding to the above board for the slots they have. Quick example:
OXO
__O
X_X
X: 0b010000101
O: 0b101001000
I also represent whose turn it is with 0b111111111 and 0b000000000.
So with that data I create an AST of logical operations:
AST = [ "|m", "&m", "^m",
"|e", "&e", "^e",
"|s", "&s", "^s",
"|t", "&t", "^t" ]
m = current players board
e = enemy players board
s = a slot (per above chart)
t = turn
During mutation one of the three operators (|,&,^) and an arbitrary number can
also be added. So you might end up with something like this (completely made
up example):
"|m&m|s^e^234|t|t"
I process this using #eval (first character gets removed). For each turn I
loop through each available slot on the board (s) and pick the one that
returns the highest value. Perhaps not the most elegent design, but I'm
pretty certain it is a sufficiant formalism.
Of course that doesn't help with heredity b/c a slight change to these little
programs has drastic effects. We need something with smoother variance. So I
gave each agent any number of these little programs and average out the
results.
I'm not quite finished with my program. And unfortunately I won't be able to
get to it til tommorrow --but I'll post it then if you would like to look at
it.
What approach have you been working on?
T.
Following up on this with my findings. I believe my results may have been correct after all. A bug in my player code was making it look otherwise, I think.
James Edward Gray II
On Dec 12, 2004, at 8:59 PM, James Edward Gray II wrote:
Okay, I think I have a working solution. My problem is in another area. My thinking about Tic-Tac-Toe itself seems flawed.
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. 
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
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???
If I understand your code correctly, you choose with highest probability the
worst move ;). You should either use moves.pop or sort in reverse order.
Note that I used exactly the opposite evaluation function: -1000 for loss and
100 for win, because it is impossible to win against a decent player and I
wanted to avoid losses and tend to play draws. Though I don't know if this
really makes a difference compared with -1 0 1 or other numbers. I hope my
choice does not lead to weird psychoanalysis of me 
Best Regards,
Brian
On Mon, 13 Dec 2004 23:27:19 +0900 Thomas Leitner <t_leitner@gmx.at> 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???Here is the code for the AI player:
class AIPlayer < Player
def initialize( game, sign )
super( game, sign )
@stats = {}
@cur_stats =
enddef 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]
enddef 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 =
endend
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 8In 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.
--
Brian Schröder
http://www.brian-schroeder.de/
I have attached my solution to this Ruby Quiz.
My first solution for this problem did not quite work out as I wanted it
to (I still do not know why it does not work correctly... 
).
Therefore I tried another thing and this one works.
If you want to try the AI, chose it as first player and let it play
against the Random Player until the Random Player does not win anymore.
Than swap positions, ie. AI as second player and Random Player as first
player, and wait again. After that the AI should be (nearly perfect!
One word to AIPlayer#game_finished: I tried different values for the
winning and losing scores. When the winning score was set to 100 and the
losing score to -100, the AI did not learn correctly. Therefore, the
losing score is now much higher than the winning score, as the AI then
tends to avoid loses (this was also pointed out by Brian Schröder in
ruby-talk#117748).
Bye,
Thomas
tictactoe.rb (5.22 KB)
On Fri, 10 Dec 2004 23:29:02 +0900 > Ruby Quiz <james@grayproductions.net> 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.
>
> Submissions can have any interface, but should be able to play
> against humans interactively. However, I also suggest making it
> easy to play against another AI, so you can "teach" the program
> faster.
>
> Being able to monitor the learning progression and know when a
> program has mastered the game would be very interesting, if you can
> manage it.
--
\ Thomas Leitner -- thomas [underscore] leitner [at] gmx [dot] at
/ "Life is what happens to you while you're busy making other plans"
> Oh, I couldn't resist this cribbling in my fingers...
But I'll be blamed, of course.
> Can we access the state of the world
The board? I can't think of how you would "make legal moves" without
it.
I expect the world to tell me what the legal moves are. Otherwise my agent
would have knowledge of workings of the world that she should not have.
> or can we access the action the opponent took. If we can't access
> anything, it will be quite hard to play perfect.If you see the board at move N and move N + 1, I suspect you'll know
what your opponent did.
Well, no ;). If we don't know anything about the game played we also don't know
what moves are legal moves for the opponent, and in what the moves result. The
whole thing gets even harder if the world is probabilistic and we can't be
shure that our moves always result in the same change in the world.
But for the sake of simplicity I simply let my ai act, as if the world wasn't
probabilistic, and the good thing is - its right indeed.
Regards,
Brian
On Sat, 11 Dec 2004 00:42:04 +0900 James Edward Gray II <james@grayproductions.net> wrote:
On Dec 10, 2004, at 9:19 AM, Brian Schröder wrote:
--
Brian Schröder
http://ruby.brian-schroeder.de/
Giovanni Intini wrote:
Attached is such a server, and you are welcome to play a running version
at fugal.net:1276. If you notice bugs please let me know - it has been
through some rudimentary testing but not exhaustive testing.I tried testing it by connecting twice to a server running locally and
it didn't notice a victory by player X on the right column (0,2 - 1,2
- 2,2). I had to continue playing until it eventually ended in a draw
Oops. Patch.
Sat Dec 11 17:04:53 MST 2004 hans@fugal.net
* column check bug
Also rearranged the row and column checks to be more logical.
diff -rN -u rubyquiz-old/tictactoe/server.rb rubyquiz-new/tictactoe/server.rb
--- rubyquiz-old/tictactoe/server.rb 2004-12-11 17:08:09.000000000 -0700
+++ rubyquiz-new/tictactoe/server.rb 2004-12-11 17:02:52.000000000 -0700
@@ -22,16 +22,18 @@
return @o if s.include? "O"*@z
false
end
On Sun, 12 Dec 2004 04:12:28 +0900, Hans Fugal <fugalh@xmission.com> wrote:
+
+ # check on the rows
+ @board.each {|row| ret = check(row) and return ret}
+
+ # check on the columns
+ @cols.times do |col|
+ s = @board.inject("") {|s,row| s << row[col]}
+ ret = check(s) and return ret
+ end
+
@rows.times do |x|
- # check on the row
- ret = check(@board) and return ret
@cols.times do |y|
- # check on the column
- if x == 0
- s = @board.collect {|row| row[y]}.join ""
- ret = check(s) and return ret
- end
-
# check diagonally down and to the right
if @cols - y >= @z and @rows - x >= @z
s = ''
Brian Schröder wrote:
It would be good to be able to play against eachother when this is all over, so I propose the following 'protocol'. It's not complicated and probably not ready for tournament tic-tac-toe ;-), but it should do nicely.
3 entities - a game server and two players. The game waits for players to connect. Upon connection the game sends an arbitrary hello line, then the character representing this player, and the board size:
This is a good idea. Let me propose one enhancement to the protocol. If we
would submit the active player each time together with the board it would make
the client actions simpler. (Though now I've got the Idea that the active
player is always Player |non-nil-positions| mod 2...
Well, the idea is that if it's your turn to move you will receive "move". If it's not, you won't. But if you prefer 'move X' to be sent to both players when it's X's turn, we can apply this patch:
diff -rN -u rubyquiz-old/tictactoe/server.rb rubyquiz-new/tictactoe/server.rb
--- rubyquiz-old/tictactoe/server.rb 2004-12-11 17:02:52.000000000 -0700
+++ rubyquiz-new/tictactoe/server.rb 2004-12-11 17:10:51.000000000 -0700
@@ -100,7 +100,7 @@
[@x,@o].each {|p| p.puts state}
move = nil
until move
- cur.puts "move"
+ [@x,@o].each {|p| p.puts "move #{cur == @x ? @x : @o}"
move = cur.gets
move = nil unless make_move(cur,move)
end
On Sun, 12 Dec 2004 04:12:28 +0900 > Hans Fugal <fugalh@xmission.com> wrote:
Brian Schröder wrote:
I encountered some inconsistencies with x,y addressing of your board.
I think, in retrospect, that what you thought were inconsistencies were just the result of my server using row-major order, whereas yours uses an inverted cartesian coordinate system. Either one is of course valid. It would be good to choose one or the other. Your server is much better code than mine and includes things I only dreamed of like threads. So I'll run both - Brians on fugal.net:1277 and mine on fugal.net:1276
As a bit of trivia, 1276 is (1024 + ?T*3) (3 T's for tic-tac-toe)
I forgot to add my client library, for easy interfacing of your tic-tac-toe
solver to the server.
Regards,
Brian
tictactoe-client.rb (1.52 KB)
tictactoe-interface.rb (2.48 KB)
On Sun, 12 Dec 2004 09:47:26 +0900 Brian Schröder <ruby@brian-schroeder.de> wrote:
On Sun, 12 Dec 2004 04:12:28 +0900 > Hans Fugal <fugalh@xmission.com> wrote:
> It would be good to be able to play against eachother when this is all
> over, so I propose the following 'protocol'. It's not complicated and
> probably not ready for tournament tic-tac-toe ;-), but it should do nicely.
>
> [Snip]I encountered some inconsistencies with x,y addressing of your board. So I
wipped up an improved version of the server. If you'd like to set it up on
your address, it would be fun to test our programs against each other.Regards,
Brian
PS: As it are two files, I'll append them. I hope this is also readably via
Newsgroup. I'll put up the server tomorrow also on my website. But now some
sleep.Regards,
Brian
--
Brian Schröder
http://www.brian-schroeder.de/
The quiz will stick to it's normal schedule, but as this doesn't involve any deadlines, it shouldn't affect you.
James Edward Gray II
P.S. On a related note, Ruby Quiz will observe the Christmas holiday. There will be no quiz the weekend of December 25th.
On Dec 11, 2004, at 3:15 PM, trans. (T. Onoma) wrote:
I'm up for this if I we can a get a couple day extension on the quiz.
Your idea with the operators is very good. Please post your program
when you are finished!
I used a very simple approach: each individual consists of a sequential
number of rules, which are looked through one after another, and the
first rule that fires is executed. Each rule consists of 9 fields that
are used as a match-template for the world. For example a template
looks like this:
[[EMPTY, DONT_CARE, DONT_CARE, DONT_CARE, X, X, O, X, O], 3]
That means that the template matches if the first field of the world is
empty, field 2, 3, 4 are irrelevent, field 4 has to be an X, and so on.
If the template matches the world, the rule triggeres and the player
tries to put its sign to field 3.
I have implemented the standard operators mutation, crossover, roulette
wheel selection, and co-evolution, but over time the population always
gets stuck in a local maximum very early, the solutions are barely able
to play two moves.
martinus
Thanks for your help! However, after I changed the code to use
moves.pop, nothing changed. I.e. the learning AI player was as bad as
was before.
Thanks for helping,
Thomas
On Tue, 14 Dec 2004 09:04:53 +0900 Brian Schröder <ruby@brian-schroeder.de> wrote:
If I understand your code correctly, you choose with highest
probability the worst move ;). You should either use moves.pop or sort
in reverse order.Note that I used exactly the opposite evaluation function: -1000 for
loss and 100 for win, because it is impossible to win against a decent
player and I wanted to avoid losses and tend to play draws. Though I
don't know if this really makes a difference compared with -1 0 1 or
other numbers. I hope my choice does not lead to weird psychoanalysis
of meBest Regards,
Brian
--
Brian Schröder
http://www.brian-schroeder.de/
--
\ Thomas Leitner -- thomas [underscore] leitner [at] gmx [dot] at
/ "Life is what happens to you while you're busy making other plans"
Just FYI. Here's my latest game with your AI. It plays well, as you can see, but an exception is thrown:
# One game or endless (o, e)? o
# Welcome to TicTacToe
# Valid players: Random Move Player, Learning AI Player, Human Mind Player
# Choose first player (enter shortest unambiguous text) : learn
# Choose second player (enter shortest unambiguous text) : human
On Dec 14, 2004, at 7:17 PM, Thomas Leitner wrote:
I have attached my solution to this Ruby Quiz.
---
-0-
---
Valid moves: 0,1,2,3,5,6,7,8
0
10-
-0-
---
Valid moves: 2,3,5,6,7,8
7
10-
-0-
01-
Valid moves: 2,3,5,8
2
101
-00
01-
Valid moves: 3,8
3
draw
tictactoe.rb:210:in `play_tictactoe': undefined local variable or method `game' for #<UserInterface:0x35021c> (NameError)
from tictactoe.rb:250
James Edward Gray II
I'm using a Board object, in my playing around. My goal in writing the quiz was to outlaw you teaching your program any strategy. It must learn that.
I personally am okay with seeing the board, but you make your personal challenge as hard as you like it!
James Edward Gray II
On Dec 10, 2004, at 10:11 AM, Brian Schröder wrote:
I expect the world to tell me what the legal moves are. Otherwise my agent
would have knowledge of workings of the world that she should not have.
I think you know the rules and the board but you don't know which moves are good and which are not.
ps: special sig...
Jannis Harder
"bp6siZmijp5CiZlCiW5CgAAChpbiiZYiiZZCi5aCZ2bs".unpack("m")[0].
unpack("C*").map{|x|x.chr}.join.unpack("B*")[0].scan(/.{24}/){i=7
$&.scan(/..../){print"\e[3#{i-=1};1;40m ";$&.each_byte{|z|
print" #"[z-?0,1]*2}};puts"\e[0m"}
Hans Fugal wrote:
Brian Schröder wrote:
It would be good to be able to play against eachother when this is all over, so I propose the following 'protocol'. It's not complicated and probably not ready for tournament tic-tac-toe ;-), but it should do nicely.
3 entities - a game server and two players. The game waits for players to connect. Upon connection the game sends an arbitrary hello line, then the character representing this player, and the board size:
This is a good idea. Let me propose one enhancement to the protocol. If we
would submit the active player each time together with the board it would make
the client actions simpler. (Though now I've got the Idea that the active
player is always Player |non-nil-positions| mod 2...Well, the idea is that if it's your turn to move you will receive "move". If it's not, you won't. But if you prefer 'move X' to be sent to both players when it's X's turn, we can apply this patch:
This will teach me to test a patch first!
diff -rN -u rubyquiz-old/tictactoe/server.rb
rubyquiz-new/tictactoe/server.rb
--- rubyquiz-old/tictactoe/server.rb 2004-12-11 17:02:52.000000000 -0700
+++ rubyquiz-new/tictactoe/server.rb 2004-12-11 17:10:51.000000000 -0700
@@ -100,7 +100,7 @@
[@x,@o].each {|p| p.puts state}
move = nil
until move
- cur.puts "move"
+ [@x,@o].each {|p| p.puts "move #{cur == @x ? 'X' : 'O'}"}
move = cur.gets
move = nil unless make_move(cur,move)
end
On Sun, 12 Dec 2004 04:12:28 +0900 >> Hans Fugal <fugalh@xmission.com> wrote:
Thank you! Call it a dumb question, but how are row-major, row-minor and
(inverted)-cartesion coordinate system defined.
I thought, row major would mean, that you have each row after another.
I could then simply adapt the adressing, to change to your protocol. This would
break no code of mine, and we could have only one server left.
Regards,
Brian
On Sun, 12 Dec 2004 12:32:22 +0900 Hans Fugal <fugalh@xmission.com> wrote:
Brian Schröder wrote:
> I encountered some inconsistencies with x,y addressing of your board.I think, in retrospect, that what you thought were inconsistencies were
just the result of my server using row-major order, whereas yours uses
an inverted cartesian coordinate system. Either one is of course valid.
It would be good to choose one or the other. Your server is much better
code than mine and includes things I only dreamed of like threads.
So I'll run both - Brians on fugal.net:1277 and mine on fugal.net:1276As a bit of trivia, 1276 is (1024 + ?T*3) (3 T's for tic-tac-toe)
--
Brian Schröder
http://www.brian-schroeder.de/