About two weeks ago, I was out skiing with Gustaf and some friends of him. We ended up playing a lot of four in a row, a really funny and simple game. This game made me think about how to develop a min max AI, and suddenly I had written down the pseudo code for such an AI in my notebook. Here is a picture of the game is supposed to be played (from wikipedia):
Now, back home at my computer, I started digging into the ruby documentations, and after not more than a few hours I had finished the first version of the AI! Turns out Ruby isn't that hard to learn, at least not if you just want to get some basic things done. It's like writing c#, except you skip the types, and instead of writing void foo(int x) { ... } you write def foo(x) ... end, and so on...Here is how my final version of the game looks when you run it:
C:\Documents and Settings\Christian\Desktop>ruby 4irad.rb
Run against ai (A), another player (P) or let two AIs play against eachother (X)
A
Enter AI 1 level (1 to 5):
3
Enter name of human player (default Human 1):
---------------
|0 1 2 3 4 5 6|
---------------
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
---------------
AI 1 (3) played: 3
---------------
|0 1 2 3 4 5 6|
---------------
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | |O| | | |
---------------
Human 1, make your move:
2
Human 1 played: 2
---------------
|0 1 2 3 4 5 6|
---------------
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |X|O| | | |
---------------
AI 1 (3) played: 3
---------------
|0 1 2 3 4 5 6|
---------------
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | |O| | | |
| | |X|O| | | |
---------------
Human 1, make your move:
and so on...
I wonder how much code can you post in a blog, without the post becoming too long? I would like to post the code as an attachment, but I'm not sure you can do that in blogger, so I'll simply put it here. To try it out, copy the code to a file, i.e. 4inarow.rb, then run it using ruby 4inarow.rb. Enjoy ;)
$debugEnabled = false
def debug(text)
if $debugEnabled then
puts ">>> " + text
end
end
class State
attr_reader :cols, :rows, :player, :winner, :lastPlayed, :isFull
Player1 = "Player 1"
Player2 = "Player 2"
def initialize
@cols = []
(0..6).each { @cols << [] }
@rows = []
(0..5).each { @rows << Array.new(7, nil) }
@player = Player1
@winner = nil
@isFull = false
end
def deep_copy
return Marshal.load( Marshal.dump( self ) )
end
def to_s
return "---------------\n" +
"|" + (0..6).to_a.join(" ") + "|\n" +
"---------------\n" +
@rows.reverse.collect{|row| "|" + row.collect{|r| if !r then " " elsif r == Player2 then "X" else "O" end}.join("|") + "|"}.join("\n") + "\n" +
"---------------"
end
def canPlay( i )
return @winner == nil && @cols[i].length < 6
end
def play( i )
if canPlay i then
rowIndex = @cols[i].length
@cols[i] << @player
@rows[rowIndex][i] = @player
@lastPlayed = i
switchPlayer
updateWinner
updateIsFull
end
end
def updateIsFull
for p in @rows[5]
if !p then return end
end
@isFull = true
end
def findWinner( row )
for i in 0..(row.length-4)
p = nil
n = 0
for j in 0..3
rp = getPlayed(row[i+j])
if rp.class != Fixnum then
if !p then
p = rp
elsif p != rp
p = 0
break
end
if rp != 0 then
n += 1
end
end
end
if p != 0 and n == 4 then
return p
end
end
return nil
end
def updateWinner
for row in getAllRanges
p = findWinner row
if p then
@winner = p
end
end
end
def switchPlayer
if @player == Player1 then
@player = Player2
else
@player = Player1
end
end
def getPlayed(cell)
c = cell[0]
r = cell[1]
col = @cols[c]
if r >= col.length then
return r - col.length + 1
end
return @cols[c][r]
end
def posValid( c, r )
return c >= 0 && c <= 6 && r >= 0 && r <= 5
end
def getDiagonal( c, r, dc )
d = []
while posValid( c, r )
d << [c, r]
c += dc
r += 1
end
return d
end
def getAllDiagonalsRanges
diags = []
for r in 0..5
diags << getDiagonal( 0, r, 1 )
end
for c in 1..6
diags << getDiagonal( c, 0, 1 )
end
for r in 0..5
diags << getDiagonal( 6, r, -1 )
end
for c in 0..5
diags << getDiagonal( c, 0, -1 )
end
return diags
end
def getAllColsRanges
return (0..6).collect{|c| (0..5).collect{|r| [c, r]}}
end
def getAllRowsRanges
return (0..5).collect{|r| (0..6).collect{|c| [c, r]}}
end
def getAllRanges
return getAllColsRanges +
getAllRowsRanges +
getAllDiagonalsRanges
end
end
class Node
attr_reader :state, :children, :isLeaf
def initialize( state, player )
if !player then
raise "player is nil"
end
@state = state
@isLeaf = true
@children = {}
@player = player
end
def getPoints( row )
points = 0.0
for i in 0..(row.length-4)
p = nil
n = 0
divider = 1
for j in 0..3
rp = @state.getPlayed(row[i+j])
if rp.class == Fixnum then
divider *= rp
else
if !p then
p = rp
elsif !rp then
elsif p != rp
p = nil
break
end
if rp then
n += 1
end
end
end
if p then
blockPoints = calculatePoints n / divider
if p == @player then
points += blockPoints
else
points = points - blockPoints
end
end
end
if points.infinite? then
debug "Found winner: " + points.to_s + ": " + row.join("|")
end
return points
end
def calculatePoints( n )
return n.to_f**3 / (4 - [n,4].min)
end
def nodePoints
points = 0.0
for row in state.getAllRanges
p = getPoints(row)
if p != 0 then
#debug row.collect{|r| if r then r else " " end}.join("|") + " " + p.to_s
end
newPoints = points + p
if newPoints.nan? then
raise "points + p == NaN: points=" + points.to_s + " p=" + p.to_s
end
points = newPoints
end
#puts state
#puts "Points: " + points.to_s
return points
end
def allChildPoints
return children.values.collect {|child| child.totalPoints}
end
def isMyTurn
return state.player == @player
end
def totalPoints
if @totalPoints then
return @totalPoints
end
p = nil
if @isLeaf then
p = nodePoints
else
if isMyTurn then
p = allChildPoints.max
else
p = allChildPoints.min
end
end
if !p then
raise "nil points returned"
end
@totalPoints = p
return p
end
def grow
if @totalPoints then
#puts "Gah, totalPoints is set"
@totalPoints = nil
end
if @isLeaf && !@state.winner
#debug "Growing leaf: " + self.to_s
for i in 0..6
if @state.canPlay i then
childState = @state.deep_copy
childState.play i
child = Node.new(childState, @player)
children[i] = child
end
end
@isLeaf = false
else
for child in @children.values
child.grow
end
end
end
def findNodeWithState( state )
if state.lastPlayed then
return @children[state.lastPlayed]
else
return nil
end
end
def to_s
return "Played: " + @state.lastPlayed.to_s + " Points: " + totalPoints.to_s
end
end
class AIPlayer
def initialize( level, name )
@level = level
@name = name
end
def to_s
return @name + " (" + @level.to_s + ")"
end
def selectBestNode
# Add some randomness
bestChild = nil
bestChildCount = nil
for child in @node.children.values
#puts child.state
#puts child.totalPoints
if !bestChild then
bestChild = child
bestChildCount = 1
else
if child.totalPoints > bestChild.totalPoints then
bestChild = child
bestChildCount = 1
elsif child.totalPoints == bestChild.totalPoints then
bestChildCount = bestChildCount + 1
if rand(bestChildCount) == 0 then
bestChild = child
end
end
end
end
#Just to make sure
if !bestChild then
raise "bestChild is nil"
end
debug "Best points: " + bestChild.totalPoints.to_s
@node = bestChild
end
def play(state)
if state.lastPlayed then
debug "Finding last played node"
@node = @node.findNodeWithState(state)
@node.grow
end
debug "Finding the best node"
selectBestNode
@node.grow
state.play @node.state.lastPlayed
end
def setupGame(state, player)
@node = Node.new(state, player)
debug "Creating min max tree (" + (7**@level).to_s + " nodes)..."
(1..@level).each{ @node.grow }
end
end
class HumanPlayer
def initialize(name)
@name = name
end
def to_s
return @name
end
def play(state)
puts @name + ", make your move:"
begin
toPlay = gets
if toPlay == "q\n" then
exit
end
toPlay = toPlay.to_i
if !state.canPlay toPlay
puts "Can't play " + toPlay.to_s + ". Select another:"
selectOther = true
else
state.play toPlay
end
end while selectOther
end
def setupGame(state, player)
end
end
def runGame
puts "Run against ai (A), another player (P) or let two AIs play against eachother (X)?"
gameType = readline.strip
case gameType
when "A", "a"
player1 = createAIPlayer
player2 = createHumanPlayer
when "P", "p"
player1 = createHumanPlayer
player2 = createHumanPlayer
when "X", "x"
player1 = createAIPlayer
player2 = createAIPlayer
else
puts "Invalid input: #{gameType}"
exit
end
players = [player1, player2]
state = State.new
player1.setupGame(state, State::Player1)
player2.setupGame(state, State::Player2)
while (!state.winner && !state.isFull)
for player in players
puts state
player.play(state)
puts player.to_s + " played: " + state.lastPlayed.to_s
if state.winner then break end
end
end
if state.winner
puts state
puts "Winner: " + state.winner.to_s
elsif state.isFull
puts state
puts "Draw!"
end
end
$aiCounter = 0
def createAIPlayer
$aiCounter = $aiCounter + 1
name = "AI " + $aiCounter.to_s
puts "Enter " + name + " level (1 to 5):"
level = readline.to_i
return AIPlayer.new(level, name)
end
$humanCounter = 0
def createHumanPlayer
$humanCounter = $humanCounter + 1
defaultName = "Human " + $humanCounter.to_s
puts "Enter name of human player (default " + defaultName + "):"
name = readline.strip
if !name || name == "" then
name = defaultName
end
return HumanPlayer.new(name)
end
def runTests
state = State.new
state.play(3)
state.play(3)
state.play(4)
state.play(4)
state.play(5)
state.play(5)
state.play(6)
#test getPlayed
if state.getPlayed([3, 0]) != State::Player1 then raise "getPlayed doesn't work" end
if state.getPlayed([3, 1]) != State::Player2 then raise "getPlayed doesn't work" end
if state.getPlayed([3, 2]) != 1 then raise "getPlayed doesn't work" end
if state.getPlayed([3, 2]).class != Fixnum then raise "getPlayed doesn't work" end
#test findWinner
winningRow = (3..6).collect{|c| [c, 0]}
if !state.findWinner(winningRow) then raise "findWinner doesn't work. winningRow=" + winningRow.to_s end
#test state.winner
if state.winner == nil then raise "winner should be set" end
puts "All tests ok"
end
runGame
#runTests
