6
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Readability

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++ {
    wg.Add(1)
    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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.