Skip to content

Instantly share code, notes, and snippets.

@benhoyt benhoyt/connect4.go
Last active Jan 25, 2018

Embed
What would you like to do?
Connect 4 solver
// A little "Connect Four" game
package main
import (
"bufio"
"flag"
"fmt"
"os"
"strconv"
"strings"
)
const (
Width = 7
Height = 6
// Piece
Empty = 0
You = 1
Me = 2
// Endings
Continue = 0
Tie = 1
Win = 2
)
type (
Piece uint8
Ending int
)
var (
grid [Width * Height]Piece
scanner *bufio.Scanner = bufio.NewScanner(os.Stdin)
quiet bool
start bool
lookAhead int
)
func main() {
flag.BoolVar(&quiet, "quiet", false, "don't show prompts or board on stderr")
flag.BoolVar(&start, "start", false, "start the game (make the first move)")
flag.IntVar(&lookAhead, "lookahead", 6, "number of moves to look ahead")
flag.Parse()
if start {
placeMove(3, Me)
vprintf("My move: ")
fmt.Printf("3\n")
}
exitCode := 0
for {
draw()
// Their move
for {
vprintf("Enter your move column (0..6): ")
move := readMove()
if move < 0 {
continue
}
if placeMove(move, You) {
break
}
vprintf("Couldn't make move at column %d\n", move)
}
end := getEnding(You)
if end == Tie {
vprintf("Tie after your move\n")
exitCode = 3
break
} else if end == Win {
vprintf("You won!\n")
exitCode = 2
break
}
// Our move
move := makeMove()
end = getEnding(Me)
if end == Tie {
vprintf("Tie after my move\n")
exitCode = 3
break
} else if end == Win {
vprintf("I won!\n")
exitCode = 1
break
}
vprintf("My move: ")
fmt.Printf("%d\n", move)
}
draw()
os.Exit(exitCode)
}
func vprintf(format string, args ...interface{}) {
if !quiet {
fmt.Fprintf(os.Stderr, format, args...)
}
}
func put(x, y int, p Piece) {
grid[y*Width+x] = p
}
func get(x, y int) Piece {
return grid[y*Width+x]
}
func draw() {
if quiet {
return
}
for y := 0; y < Height; y++ {
fmt.Fprint(os.Stderr, "| ")
for x := 0; x < Width; x++ {
switch get(x, y) {
case Empty:
fmt.Fprint(os.Stderr, ". ")
case Me:
fmt.Fprint(os.Stderr, "M ")
case You:
fmt.Fprint(os.Stderr, "Y ")
}
}
fmt.Fprint(os.Stderr, "|\n")
}
fmt.Fprint(os.Stderr, "+-", strings.Repeat("-", Width*2), "+\n")
fmt.Fprint(os.Stderr, "| ")
for x := 0; x < Width; x++ {
vprintf("%d ", x)
}
fmt.Fprint(os.Stderr, "|\n")
}
func readMove() int {
if !scanner.Scan() {
if err := scanner.Err(); err != nil {
vprintf("error reading standard input: %v\n", err)
}
return -1
}
move, err := strconv.Atoi(scanner.Text())
if err != nil {
return -1
}
if move < 0 || move >= Width {
return -1
}
return move
}
func placeMove(x int, p Piece) bool {
for y := 0; y < Height; y++ {
if get(x, y) != Empty {
if y == 0 {
return false
}
put(x, y-1, p)
return true
}
}
put(x, Height-1, p)
return true
}
func liftMove(x int) {
for y := 0; y < Height; y++ {
if get(x, y) != Empty {
put(x, y, Empty)
return
}
}
panic(fmt.Sprintf("invalid liftMove() %d", x))
}
func getEnding(p Piece) Ending {
numEmpty := 0
for y := 0; y < Height; y++ {
for x := 0; x < Width; x++ {
if get(x, y) == Empty {
numEmpty++
}
if get(x, y) != p {
continue
}
if x <= Width-4 && get(x+1, y) == p && get(x+2, y) == p && get(x+3, y) == p {
// Winning four to the right
return Win
}
if x <= Width-4 && y <= Height-4 && get(x+1, y+1) == p && get(x+2, y+2) == p && get(x+3, y+3) == p {
// Winning four down and to the right
return Win
}
if y <= Height-4 && get(x, y+1) == p && get(x, y+2) == p && get(x, y+3) == p {
// Winning four down
return Win
}
if x >= 3 && y <= Height-4 && get(x-1, y+1) == p && get(x-2, y+2) == p && get(x-3, y+3) == p {
// Winning four down and to the left
return Win
}
}
}
if numEmpty == 0 {
return Tie
}
return Continue
}
func makeMove() int {
move, _ := pickMove(Me, lookAhead)
if move >= 0 {
placeMove(move, Me)
}
return move
}
func pickMove(piece Piece, lookahead int) (move, score int) {
scores := make([]int, Width)
for i := range scores {
if !placeMove(i, piece) {
scores[i] = -2000000
continue
}
end := getEnding(piece)
if end == Win {
liftMove(i)
return i, 1000000
} else if end == Tie {
// scores[i] is 0 already
liftMove(i)
continue
}
if lookahead > 0 {
other := Piece(You)
if piece == You {
other = Me
}
_, otherScore := pickMove(other, lookahead-1)
scores[i] = -otherScore
} else {
scores[i] = -getScore(piece)
}
liftMove(i)
}
highest := -2000000
highestIndex := -1
for i := range scores {
if scores[i] > highest {
highest = scores[i]
highestIndex = i
}
}
if highest == -2000000 {
return -1, highest
}
return highestIndex, highest
}
var runScores = map[int]int{
1: 1,
2: 10,
3: 100,
4: 1000,
5: 10000,
}
func getScore(piece Piece) int {
type pos struct{ x, y int }
counted := make(map[pos]bool)
score := 0
for y := 0; y < Height; y++ {
for x := 0; x < Width; x++ {
p := get(x, y)
if p == Empty {
continue
}
if _, ok := counted[pos{x, y}]; ok {
// Already counted
continue
}
// Scan for run to the right
run := 1
for i := 1; i < 4 && x+i < Width; i++ {
q := get(x+i, y)
if q != p {
if x > 0 && get(x-1, y) == Empty {
run++
}
if q == Empty {
run++
}
break
}
counted[pos{x, y}] = true
run++
}
score += runScores[run]
// Scan for run down and to the right
run = 1
for i := 1; i < 4 && x+i < Width && y+i < Height; i++ {
q := get(x+i, y+i)
if q != p {
if x > 0 && y > 0 && get(x-1, y-1) == Empty {
run++
}
if q == Empty {
run++
}
break
}
counted[pos{x, y}] = true
run++
}
score += runScores[run]
// Scan for run down
run = 1
for i := 1; i < 4 && y+i < Height; i++ {
q := get(x, y+i)
if q != p {
if y > 0 && get(x, y-1) == Empty {
run++
}
if q == Empty {
run++
}
break
}
counted[pos{x, y}] = true
run++
}
score += runScores[run]
// Scan for run down and to the left
run = 1
for i := 1; i < 4 && x-i >= 0 && y+i < Height; i++ {
q := get(x-i, y+i)
if q != p {
if x+1 < Width && y > 0 && get(x+1, y-1) == Empty {
run++
}
if q == Empty {
run++
}
break
}
counted[pos{x, y}] = true
run++
}
score += runScores[run]
}
}
return score
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.