Tic Tac Toe in Go with Minimax AI

tictactoe.go

package main

import (
	"errors"
	"fmt"
	"math"
	"strconv"
)

func playerToken(b bool) (c string) {
	if b {
		return "x"
	} else {
		return "o"
	}
}

func main() {
	game := [3][3]string{{"", "", ""}, {"", "", ""}, {"", "", ""}}
	isRunning := true
	player := true

	var x, y int
	for isRunning {
		prettyPrint(game)
		if player {
			x, y = getInput(player)
		} else {
			x, y = getAI(game)
		}

		for game[x][y] != "" {
			fmt.Printf("\nSquare already taken, try again.")
			x, y = getInput(player)
		}

		game[x][y] = playerToken(player)

		winner := evaluate(game)
		switch winner {
		case "":
			empties := getEmptyCells(game)
			if len(empties) < 1 {
				isRunning = false
				fmt.Printf("\nDraw!\n")
			}
			player = !player
		default:
			isRunning = false
			prettyPrint(game)
			fmt.Printf("\nGame over! Player %s wins\n", winner)
		}
	}
}

func getAI(game [3][3]string) (i, j int) {
	nextMoves := getEmptyCells(game)
	max_score := -1000000.0
	var max_move int
	for _, ij := range nextMoves {
		ij, score := minimax(game, ij, 0, true)
		if score > max_score {
			max_move = ij
			max_score = score
		}
	}

	i, j = unCellValue(max_move)
	return
}
func minimax(state [3][3]string, ij int, depth float64, maximise bool) (max_move int, max_score float64) {

	max_move = ij
	nextState := state
	i, j := unCellValue(ij)
	nextState[i][j] = playerToken(!maximise)

	winner := evaluate(nextState)
	switch winner {
	case playerToken(!maximise):
		max_score = 1.0
		return
	case playerToken(maximise):
		max_score = -1.0
		return
	case "":
		nextMoves := getEmptyCells(nextState)
		if len(nextMoves) == 0 {
			max_score = 0
			return
		}
		for _, xy := range nextMoves {
			_, score := minimax(nextState, xy, depth+1, !maximise)
			max_score = max_score + score*-1
		}
	}
	max_score = max_score * 0.5

	return
}

func getEmptyCells(game [3][3]string) (cells []int) {
	for i, row := range game {
		for j, cell := range row {
			if cell == "" {
				cells = append(cells, cellValue(i, j))
			}
		}
	}
	return
}

func cellValue(i, j int) (ij int) {
	ij = (i+1)*10 + (j + 1)
	return
}

func unCellValue(ij int) (i, j int) {
	j = int(math.Mod(float64(ij), 10)) - 1
	i = (ij-j)/10 - 1
	return
}
func getInput(currentPlayer bool) (x, y int) {
	fmt.Printf("\nEnter a square, e.g. 1A. %s's turn: ", playerToken(currentPlayer))

	var xy string
	_, err := fmt.Scan(&xy)
	if err != nil || len(xy) != 2 {
		fmt.Printf("\nInvalid input, please try again")
		return getInput(currentPlayer)
	}

	x, xerr := strconv.Atoi(string(xy[0]))
	y, yerr := colInt(string(xy[1]))
	if xerr != nil || yerr != nil {
		fmt.Printf("\nInvalid input, please try again.")
		return getInput(currentPlayer)
	}
	return x - 1, y - 1
}

func colInt(c string) (int, error) {
	switch c {
	case "A":
		return 1, nil
	case "B":
		return 2, nil
	case "C":
		return 3, nil
	default:
		return -1, errors.New("Invalid column. Please choose A, B, or C.")
	}
}

func evaluate(game [3][3]string) (winner string) {
	wins := [][3]int{
		{11, 12, 13},
		{21, 22, 23},
		{31, 32, 33},
		{11, 21, 31},
		{12, 22, 32},
		{13, 23, 33},
		{11, 22, 33},
		{13, 22, 31}}

	var xs, ys []int
	for i, row := range game {
		for j, cell := range row {
			switch cell {
			case playerToken(true):
				xs = append(xs, cellValue(i, j))
			case playerToken(false):
				ys = append(ys, cellValue(i, j))
			}
		}
	}

	for _, winSet := range wins {
		if subset(winSet, xs) {
			winner = playerToken(true)
			return
		} else if subset(winSet, ys) {
			winner = playerToken(false)
			return
		} else {
			winner = ""
		}
	}

	return
}

func subset(first [3]int, second []int) bool {
	set := make(map[int]int)
	for _, value := range second {
		set[value] += 1
	}

	for _, value := range first {
		if count, found := set[value]; !found {
			return false
		} else if count < 1 {
			return false
		} else {
			set[value] = count - 1
		}
	}

	return true
}

func prettyPrint(game [3][3]string) {
	fmt.Printf("\n  A B C\n")
	for i, row := range game {
		fmt.Printf("%d|", i+1)
		for _, cell := range row {
			if cell == "" {
				cell = "_"
			}
			fmt.Printf("%s|", cell)
		}
		fmt.Printf("%d\n", i+1)
	}
}