# constants representing hits and misses.
HIT <- 9; MISS <- -9
placeShip <- function(board, shipIndex){
isLegal <- FALSE
giveUp <- 0
while(!isLegal & giveUp < 100){
giveUp <- giveUp+1
orientation = sample(2,1) #upright or across
if(orientation==2) {board <- t(board)}
shipLength = shipSizes[shipIndex]
shipX = sample(1:(dim(board)[1]-shipLength+1),1)
shipY = sample(1:(dim(board)[2]),1)
isLegal = prod(board[shipX:(shipX+shipLength-1), shipY] %in% c(0,HIT))
if(isLegal){
board[shipX:(shipX+shipLength-1), shipY] <- shipIndex
}
if(orientation==2) {board <- t(board)}
}
if(isLegal){
return(board)
} else{
return(FALSE)
}
}
placeAllShips <- function(board){
for(i in which(shipAlive)){
board <- placeShip(board,i)
if(!is.matrix(board)) return(FALSE)
}
if(sum(board==HIT)==0){
return(board)
} else {
return(FALSE)
}
}
buildHeatMap <- function(boardKnowledge, NMC=10000){
boardMap <- matrix(data=0, nrow=boardDim[1], ncol=boardDim[2])
for(i in 1:NMC){
placeAll <- placeAllShips(boardKnowledge)
if(is.matrix(placeAll)){
boardMap <- boardMap + (placeAll %in% (1:length(shipAlive))[shipAlive])
}
}
return(boardMap)
}
guessACoord <- function(boardKnowledge, NMC=10000){
hmap <- buildHeatMap(boardKnowledge, NMC)
#remove known hits
hmap[which(boardKnowledge==HIT)] <- 0
guessIndex <- which(hmap == max(hmap))[1]
guessX <- guessIndex %% boardDim[1]
if(guessX == 0) {guessX <- 10}
guessY <- floor((guessIndex-1) / boardDim[2])+1
return(list(c(guessX,guessY), hmap))
}
resultOfGuess <- function(guess){
x <- guess[1]; y<- guess[2]; returnstr <- ""
if(trueBoard[x,y] == 0){
boardKnowledge[x,y] <<- MISS
returnstr <- "Miss"
} else{
#Hit
returnstr <-"Hit!"
boatIndex <- abs(trueBoard[x,y])
trueBoard[x,y] <<- trueBoard[x,y] * -1
boardKnowledge[x,y] <<- HIT
if(sum(trueBoard == boatIndex)==0){
#sunk it
boardKnowledge[which(trueBoard==(-boatIndex))] <<- -boatIndex
returnstr <- paste(returnstr," Sunk Boat ",boatIndex,".",sep="")
shipAlive[boatIndex] <<- FALSE
}
if(sum(trueBoard>0)==0){
#All Boats Sunk
returnstr <- paste(returnstr, "You Lose")
}
}
return(returnstr)
}12 Monte Carlo Battleship
This code will demonstrate how you can use Monte Carlo Simulation to create an AI opponent in Battleship.
First a few function that will be used throughout.
Test it out. First the setup.
library(fields)
#Define board
boardDim=c(10,10)
#Define ship sizes
shipSizes=c(5,4,3,3,2)
#Initialize ship states
shipAlive = rep(TRUE, length(shipSizes))
#initializeKnowledge
# 0 unknown
# 1,2,3, etc hit boat
boardKnowledge=matrix(data=0, nrow=boardDim[1], ncol=boardDim[2])
trueBoard <- placeAllShips(boardKnowledge)
par(mfrow=c(1,2), mar=c(.5, 3, 4, 0))
image(trueBoard, main="Ship Locations", col=tim.colors(),yaxt="n",xaxt="n");
axis(3, at=seq(0,1, length.out=10), labels=LETTERS[1:10], lwd=0, pos=1, cex.axis=.75)
axis(2, at=seq(0,1, length.out=10), labels=10:1, lwd=0, pos=0, cex.axis=.75);
image(boardKnowledge, main="Comp Knowledge", col=tim.colors(),yaxt="n",xaxt="n");
axis(3, at=seq(0,1, length.out=10), labels=LETTERS[1:10], lwd=0, pos=1, cex.axis=.75)
axis(2, at=seq(0,1, length.out=10), labels=10:1, lwd=0, pos=0, cex.axis=.75)
Play the Game!!!
turn <- 0
while(sum(shipAlive)>0 | turn < 9){
turn <- turn +1
guessList <- guessACoord(boardKnowledge,1000)
guess <- guessList[[1]]
guessResult <- resultOfGuess(guess)
print(paste("Turn ",turn,": Computer Guesses ",LETTERS[guess[1]],11-guess[2],": ",guessResult, sep=""))
flush.console()
par(mfrow=c(1,3), mar=c(.5, 3, 3, 0))
image(guessList[[2]], main="Heatmap", col=tim.colors(),yaxt="n",xaxt="n");
axis(3, at=seq(0,1, length.out=10), labels=LETTERS[1:10], lwd=0, pos=1)
axis(2, at=seq(0,1, length.out=10), labels=10:1, lwd=0, pos=0)
image(trueBoard, main="My Board", col=tim.colors(),yaxt="n",xaxt="n");
axis(3, at=seq(0,1, length.out=10), labels=LETTERS[1:10], lwd=0, pos=1)
axis(2, at=seq(0,1, length.out=10), labels=10:1, lwd=0, pos=0)
image(boardKnowledge, main="Comp Knowledge", col=tim.colors(),yaxt="n",xaxt="n")
axis(3, at=seq(0,1, length.out=10), labels=LETTERS[1:10], lwd=0, pos=1)
axis(2, at=seq(0,1, length.out=10), labels=10:1, lwd=0, pos=0)
}[1] "Turn 1: Computer Guesses F6: Hit!"
[1] "Turn 2: Computer Guesses E6: Miss"
[1] "Turn 3: Computer Guesses F7: Hit!"
[1] "Turn 4: Computer Guesses F8: Hit! Sunk Boat 3."
[1] "Turn 5: Computer Guesses D5: Miss"
[1] "Turn 6: Computer Guesses G5: Miss"
[1] "Turn 7: Computer Guesses C4: Hit!"
[1] "Turn 8: Computer Guesses C5: Hit!"
[1] "Turn 9: Computer Guesses C3: Hit!"
[1] "Turn 10: Computer Guesses C6: Miss"
[1] "Turn 11: Computer Guesses C2: Hit!"
[1] "Turn 12: Computer Guesses C1: Hit! Sunk Boat 1."
[1] "Turn 13: Computer Guesses D9: Miss"
[1] "Turn 14: Computer Guesses H4: Miss"
[1] "Turn 15: Computer Guesses B7: Hit!"
[1] "Turn 16: Computer Guesses B8: Miss"
[1] "Turn 17: Computer Guesses C7: Miss"
[1] "Turn 18: Computer Guesses B6: Hit!"
[1] "Turn 19: Computer Guesses B5: Hit! Sunk Boat 4."
[1] "Turn 20: Computer Guesses G9: Miss"
[1] "Turn 21: Computer Guesses I3: Miss"
[1] "Turn 22: Computer Guesses F2: Miss"
[1] "Turn 23: Computer Guesses I7: Miss"
[1] "Turn 24: Computer Guesses G1: Miss"
[1] "Turn 25: Computer Guesses J6: Miss"
[1] "Turn 26: Computer Guesses E10: Miss"
[1] "Turn 27: Computer Guesses A4: Miss"
[1] "Turn 28: Computer Guesses E3: Miss"
[1] "Turn 29: Computer Guesses H8: Hit!"
[1] "Turn 30: Computer Guesses H7: Hit!"
[1] "Turn 31: Computer Guesses H6: Hit!"
[1] "Turn 32: Computer Guesses H9: Hit! Sunk Boat 2."
[1] "Turn 33: Computer Guesses F4: Miss"
[1] "Turn 34: Computer Guesses G3: Miss"
[1] "Turn 35: Computer Guesses H2: Miss"
[1] "Turn 36: Computer Guesses I5: Miss"
[1] "Turn 37: Computer Guesses A9: Miss"
[1] "Turn 38: Computer Guesses B3: Miss"
[1] "Turn 39: Computer Guesses D7: Miss"
[1] "Turn 40: Computer Guesses E1: Miss"
[1] "Turn 41: Computer Guesses J4: Miss"
[1] "Turn 42: Computer Guesses E8: Miss"
[1] "Turn 43: Computer Guesses C10: Miss"
[1] "Turn 44: Computer Guesses A2: Miss"
[1] "Turn 45: Computer Guesses I9: Miss"
[1] "Turn 46: Computer Guesses J8: Miss"
[1] "Turn 47: Computer Guesses J2: Hit!"
[1] "Turn 48: Computer Guesses I2: Hit! Sunk Boat 5. You Lose"