I am trying to improve the performance of a monte carlo search algorithm that simulates random gameplays in a simple optimization game until a time limit is reached, and then returns the best outcome. The puzzle is from CodinGame.
I have been benchmarking the code for a while and have been able to make it a lot faster compared to my initial attempts, but now seem to have hit a ceiling in my abilities in improving performance. Have I made bad decisions from performance point of view?
Here's the code:
package main
import (
"fmt"
"math"
"math/rand"
"os"
"time"
)
const (
ZOMBIE_SPEED_SQ float64 = 400 * 400
PLAYER_SPEED_SQ float64 = 1000 * 1000
SHOOT_RANGE_SQ float64 = 2000 * 2000
ZOMBIES_SAFE_DIST_SQ float64 = (400 + 1000 + 2000) * (400 + 1000 + 2000)
)
var FIBS = []int{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393,
196418, 317811, 514229, 832040}
func main() {
rand.Seed(time.Now().UTC().UnixNano())
var timelimitNS time.Duration
timelimitNS = 1000E6
i, score := FindSolution(timelimitNS)
fmt.Fprintf(os.Stderr, "did %v simulations, best score %v \n", i, score)
}
// Point struct and related methods
type Point struct {
x float64
y float64
}
func (me *Point) DistSq(to *Point) float64 {
return (to.x-me.x)*(to.x-me.x) + (to.y-me.y)*(to.y-me.y)
}
func (me *Point) Move(to *Point, speedsq float64) {
distsq := me.DistSq(to)
if speedsq <= distsq {
temp := speedsq / distsq
mod := math.Sqrt(temp)
me.x = math.Trunc(me.x + mod*(to.x-me.x))
me.y = math.Trunc(me.y + mod*(to.y-me.y))
} else {
me.x = to.x
me.y = to.y
}
}
// Gamestate struct and related methods
type GameState struct {
score int
player *Point
zombies []*Point
humans []*Point
}
func CreateGameState() *GameState {
state := new(GameState)
state.score = 0
state.player = nil
state.zombies = make([]*Point, 0, 100)
state.humans = make([]*Point, 0, 100)
return state
}
func (state *GameState) Simulate(inpGen func() *Point, cutoff int) (int, []Point) {
turn := 0
tempSlice := make([]*Point, 0, 100)
tempShootSlice := make([]*Point, 0, 100)
tempSafeZombiesSlice := make([]*Point, 0, 100)
moveList := make([]Point, 0, 100)
for {
turn++
// Zombies move towards their targets
tempShootSlice = tempShootSlice[:0]
tempSafeZombiesSlice = tempSafeZombiesSlice[:0]
for _, zObj := range state.zombies {
closestObj := state.player
closestDistSq := zObj.DistSq(state.player)
// tempShootSlice is used in the shooting step
if closestDistSq <= ZOMBIES_SAFE_DIST_SQ {
tempShootSlice = append(tempShootSlice, zObj)
} else {
tempSafeZombiesSlice = append(tempSafeZombiesSlice, zObj)
}
// Find the closest human
for _, hObj := range state.humans {
dist := zObj.DistSq(hObj)
if dist <= closestDistSq {
closestObj = hObj
closestDistSq = dist
}
}
zObj.Move(closestObj, ZOMBIE_SPEED_SQ)
}
// Player moves towards a random point
inputPoint := inpGen()
moveList = append(moveList, *inputPoint)
state.player.Move(inputPoint, PLAYER_SPEED_SQ)
// Shoot zombies
tempSlice = tempSlice[:0]
killCount := 0
zombieWorth := len(state.humans) * len(state.humans) * 10
for _, zObj := range tempShootSlice {
if zObj.DistSq(state.player) <= SHOOT_RANGE_SQ {
// fmt.Printf("Shot zombie %v on turn %v \n", zObj, turn)
killCount++
state.score += zombieWorth * FIBS[killCount]
} else {
tempSafeZombiesSlice = append(tempSafeZombiesSlice, zObj)
}
}
state.zombies = state.zombies[:0]
for _, zObj := range tempSafeZombiesSlice {
state.zombies = append(state.zombies, zObj)
}
if len(state.zombies) == 0 {
// fmt.Printf("exiting because of no zombies \n")
break
}
// Eat humans
tempSlice = tempSlice[:0]
nzombies := len(state.zombies)
for _, hObj := range state.humans {
for zID, zObj := range state.zombies {
if hObj.x == zObj.x && hObj.y == zObj.y {
break
} else {
if zID == nzombies-1 {
tempSlice = append(tempSlice, hObj)
}
}
}
}
state.humans = state.humans[:0]
for _, hObj := range tempSlice {
state.humans = append(state.humans, hObj)
}
if len(state.humans) == 0 {
state.score = 0
}
// Finally, let's see if there is any
// reason to simulate further
potentialMaxScore := state.score
worth := len(state.humans) * len(state.humans) * 10
for killCount := 0; killCount < len(state.zombies); killCount++ {
potentialMaxScore += worth * FIBS[killCount]
}
if potentialMaxScore < cutoff {
break
}
}
finalscore := state.score
return finalscore, moveList
}
// This would read stdin, replaced with a hard coded test case
func (state *GameState) TakeInput() {
state.score = 0
state.player = &Point{3989, 3259}
state.zombies = state.zombies[:0]
state.zombies = append(state.zombies, &Point{9202, 826})
state.zombies = append(state.zombies, &Point{11060, 253})
state.zombies = append(state.zombies, &Point{14148, 650})
state.zombies = append(state.zombies, &Point{9669, 1968})
state.zombies = append(state.zombies, &Point{8360, 4767})
state.zombies = append(state.zombies, &Point{9804, 4154})
state.zombies = append(state.zombies, &Point{12310, 4614})
state.zombies = append(state.zombies, &Point{913, 5636})
state.zombies = append(state.zombies, &Point{2410, 5912})
state.zombies = append(state.zombies, &Point{3952, 6143})
state.zombies = append(state.zombies, &Point{9049, 5470})
state.zombies = append(state.zombies, &Point{1798, 6682})
state.zombies = append(state.zombies, &Point{6415, 7094})
state.zombies = append(state.zombies, &Point{9550, 6847})
state.humans = state.humans[:0]
state.humans = append(state.humans, &Point{3647, 384})
state.humans = append(state.humans, &Point{60, 3262})
state.humans = append(state.humans, &Point{2391, 1601})
state.humans = append(state.humans, &Point{2363, 3422})
}
// Clonefrom copies the content of one Gamestate struct to another
func (state *GameState) CloneFrom(source *GameState) {
var temp *Point
state.score = source.score
state.player = new(Point)
state.player.x, state.player.y = source.player.x, source.player.y
state.zombies = state.zombies[:0]
for _, zObj := range source.zombies {
temp = new(Point)
temp.x, temp.y = zObj.x, zObj.y
state.zombies = append(state.zombies, temp)
}
state.humans = state.humans[:0]
for _, hObj := range source.humans {
temp = new(Point)
temp.x, temp.y = hObj.x, hObj.y
state.humans = append(state.humans, temp)
}
}
func InputGenCreator() func() *Point {
var possiblePoints = make([]*Point, 0, 25)
possiblePoints = append(possiblePoints, &Point{0, 0})
possiblePoints = append(possiblePoints, &Point{4000, 0})
possiblePoints = append(possiblePoints, &Point{8000, 0})
possiblePoints = append(possiblePoints, &Point{12000, 0})
possiblePoints = append(possiblePoints, &Point{16000, 0})
possiblePoints = append(possiblePoints, &Point{0, 2000})
possiblePoints = append(possiblePoints, &Point{0, 4000})
possiblePoints = append(possiblePoints, &Point{4000, 4000})
possiblePoints = append(possiblePoints, &Point{8000, 4000})
possiblePoints = append(possiblePoints, &Point{12000, 4000})
possiblePoints = append(possiblePoints, &Point{16000, 4000})
possiblePoints = append(possiblePoints, &Point{0, 8000})
possiblePoints = append(possiblePoints, &Point{4000, 8000})
possiblePoints = append(possiblePoints, &Point{8000, 8000})
possiblePoints = append(possiblePoints, &Point{12000, 8000})
possiblePoints = append(possiblePoints, &Point{16000, 8000})
var possibleLength = len(possiblePoints)
return func() *Point {
return possiblePoints[rand.Intn(possibleLength)]
}
}
// This function repeats simulation until time limit is reached
func FindSolution(timelimitNS time.Duration) (int, int) {
timer := time.NewTimer(timelimitNS)
initialState := CreateGameState()
initialState.TakeInput()
inputGen := InputGenCreator()
workState := CreateGameState()
bestScore := 0
iterations := 0
batchSize := 100
for {
select {
case <-timer.C:
timer.Stop()
return iterations, bestScore
default:
for j := 1; j <= batchSize; j++ {
// Revert back to initial state before simulation
workState.CloneFrom(initialState)
score, _ := workState.Simulate(inputGen, bestScore)
if score > bestScore {
bestScore = score
}
iterations++
}
}
}
}
More information on the game below.
The puzzle is called "code vs zombies", a login to Codingame is needed to see the actual puzzle, but a short version of the mechanics is as follows:
The game is played on a board of 16.000 x 8.000 units. There are three kinds of objects on the board: the player, 1-100 zombies and 1-100 civilians. Each turn, the humans always stay still, while the zombies move at a speed of 400 towards the nearest human (or the player if he is closest). If a zombie reaches a human, the human dies. The player can move at a max speed of 1.000 each turn, and he will automatically kill zombies that are closer to him than 2.000 units. The kills are scored by a formula that uses the fibonacci series to give more points to bigger combos. The game ends with a score of 0 if all humans were killed. If all zombies are killed, the player gets the score that he has gained from shooting zombies.
In my code, I store the gamestate in an initialGameState struct that contains information on where the gameobjects are. Then, I repeat a simulation process until a time limit is reached that does the following:
1) take a copy of the initialGameState struct
2) play the game as described above with random inputs for the player (this is the simulate method on gameState struct)
3) if the result was better than the previous best result reached, store it
There were a couple of videos on youtube that give an idea of what the game looks like if you search for "codingame code vs zombies".
