Simple game outcome simulator

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++
}
}
}
}

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

Instead of timelimitNS, I would recommend you to use a context.WithTimeout (here is a nice video introduction: https://youtu.be/LSzR0VEraWw).

Multicore

You currently have one loop trying to find the best scores, without any goroutines (which is one of the main features of go)!

If you have a CPU with multiple cores, you may benefit from multiple workers:

// compute the scores
wg := sync.WaitGroup{}
scores := make(chan int)
for i := 0 ; i < workers; i++ {
go func(){
defer wg.Done()

workState := CreateGameState()
for {
select {
case <-ctx.Done():
return
default:
// Revert back to initial state before simulation
workState.CloneFrom(initialState)

score, _ := workState.Simulate(inputGen, bestScore)
scores <- score
}
}
}()
}

// Close the scores channel when workers are finished
go func(){
wg.Wait()
close(scores)
}

// select best score
bestScore := 0
for score := range scores {
if score > bestScore {
bestScore = score
}
}

Benchmarking

How did you benchmark? Did you look at what took the longest?

Commands like:

go test -cpuprofile=cpu.prof
go-torch your-program.test cpu.prof

go-torch beein able to generate a FlameGraph (https://github.com/uber/go-torch)

Here is a video introducing profiling in go: https://youtu.be/uBjoTxosSys?t=25m41s)