Raylib

Go

AI

Game

Minimax

Alpha-Beta Pruning

##

IntroThis was my first attempt at implementing the Minimax algorithm, as well as implementing the Alpha-Beta search optimization strategy.

Here you can see a demo of the AI winning against me.

The AI is impossible to beat, even if you start first. The closest you can get to beating it, is drawing against it, like shown below:

##

HistoryThe core game was implemented using Raylib and Go in one day and the Minimax algorithm was made the following day, although with a few bugs. After about a week of trying to fix said bugs, I managed to fix one of the dumbest mistakes, I've ever made:

```
func Minimax(ai Player, g *Game) {
max := math.Inf(-1)
bestState := State{}
+ other := otherPlayer(ai)
for _, state := range nextBoards(g.Board, ai) {
- value := float64(minimax(state.Board, ai, ai))
+ value := float64(minimax(state.Board, ai, other))
if value > max {
max = value
bestState = state
```

I was letting the AI think it can play 2 moves in a row, instead of 1, thus making it possible to beat by humans.

##

WTF is Minimax/Alpha-Beta Pruning?###

MinimaxMinimax is an algorithm for solving games that is ideally used for 2-player, turn-based, deterministic, perfect information, zero-sum games. Now that's a lot math-jargon, right? Don't worry! Here are the these terms explained:

`2-player`

and`turn-based`

are pretty self-explanatory`deterministic`

in simple terms means that every action / state can be*determined*, as opposed to`stochastic`

(`probabilistic`

/`random`

) games - such as Backgammon or anything that involes a dice for example!`perfect information`

means that our agent is given the*full*information / state, as oppoosed to environments where the agent isn't given all of the information - such as Poker or Scrabble (the agent doesn't know the other players' cards or tiles).`zero-sum`

games are games such that the gains of one player are equal to the losses of the other player

At its core minimax is basically a depth-first search, trying to brute force all possible states and find the best action to take.

You can read more about it in the GitHub repo's references section.

###

Alpha-Beta PruningAs I explained, Minimax tries to brute force all possible combinations / actions for a given state, which as you can probably guess, is very computationally expensive. There are many ways to optimize minimax, one of them is called Alpha-Beta Pruning. The basic idea is that you "prune" off / don't bother computing branches of the tree which will never be picked. In simple terms - it doesn't bother computing things if a better action was found earlier on.

Again, you can read more about it in the GitHub repo's references section.

The source code for this can be found on GitHub