Playing Chess with Go

A practical introduction to the
Go Programming Language

Christoph Hack <christoph@tux21b.org>
PyGraz MeetUp, Tuesday, May 1, 2012

ChessBuddy

ChessBuddy

My current toy project for exploring modern web technologies (HTML 5, WebSockets) and concurrent systems using Go.

Live Demo:
http://chess.tux21b.org:8000/

Ugly Code: I haven't settled on a board representation (0x88 vs. bitboard) and algorithm yet. Seeking advice!

Contributions are welcome. Getting Started:

go get github.com/tux21b/ChessBuddy

Web Servers in Go

Interlude: Go's type system

type Celsius float64

func (c Celsius) String() string {
    return fmt.Sprintf("%.3f °C", c)
}

type Fahrenheit float64

func (f Fahrenheit) String() string {
    return fmt.Sprintf("%.3f °F", f)
}

func (f Fahrenheit) ToCelsius() Celsius {
    return Celsius((f-32)*5.0/9.0)
}

func main() {
    a := Fahrenheit(451)
    b := a.ToCelsius()
    fmt.Println(a, b)
}

float64, Celsius and Fahrenheit are three disctinct types with different method sets. They just happen to have the same binary representation.

Interlude: Interfaces

The Handle() function of the net/http package can be used to register HTTP handlers. It has this signature:

func Handle(pattern string, handler Handler)

Handler is the following interface:

type Handler interface {
    ServeHTTP(ResponseWriter, *Request)
}

So we can register any object which has such a ServeHTTP() method!

Example: A simple web application

package main

import (
    "net/http"
    "html/template"
)

type Blog struct {
    Title string
    Posts []string
}

func (b *Blog) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    tmpl.Execute(w, b)
}

var tmpl *template.Template = template.Must(template.New("").Parse(`
    <h1>{{.Title}}</h1>
    <ul>{{range .Posts}}<li>{{.}}</li>{{end}}</ul>`))

func main() {
    blog := &Blog{
        Title: "Hello  世界",
        Posts: []string{"My 1st post", "My 2nd post"},
    }
    http.Handle("/", blog)
    http.ListenAndServe(":8000", nil)
}

Using functions for simple HTTP handlers

type HandlerFunc func(ResponseWriter, *Request)

func (f HandlerFunc) ServeHTTP(w ResponseWriter, r *Request) {
    f(w, r)
}

For convinience, there is also a http.HandleFunc() method which just casts a

func(ResponseWriter, *Request)

to a HandlerFunc before calling http.Handle().

package main

import "net/http"
import "fmt"

func handleIndex(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "Hello %s!\n", r.FormValue("name"))
}

func main() {
    http.HandleFunc("/", handleIndex)
    http.ListenAndServe(":5000", nil)
}

Multiplayer Chess: An easy task?

The Solution: Channels and Goroutines

Based on Communicating Sequential Processes (CSP)
by C. A. R. Hoare, 1978

Concurrency ≠ Parallelism

Structural Mismatch:

Don't communicate by sharing memory; share memory by communicating.

Simple and easy way to write and debug concurrent programs.

Example: Hooking up Players

var available = make(chan *Player, 100)

func hookUp() {
    a := <-available
    for {
        b := <-available
        if a.Alive() {
            go play(a, b) // start a new game
            a = <-available
        } else {
            a = b
        }
    }
}

func handleWS(ws *websocket.Conn) {
    available <- &Player{Conn: ws}

    // retrieve and send messages, send stats etc.
    // …
}

func main() {
    go hookUp()

    http.Handle("/ws", websocket.Handler(handleWS))
    http.ListenAndServe(":8000", nil)
}

Parallelism: G's and M's

The go scheduler's job is to match ready-to-run goroutines (G's) with waiting-for-work schedulers (M's). If there are ready G's and no waiting M's, ready() will start a new M running in a new OS thread, so that all ready G's can run simultaneously, up to a limit (GOMAXPROCS).

Let's enable parallel execution for ChessBuddy:

func main() {
    runtime.GOMAXPROCS(runtime.NumCPU())
    // …
}

Go is great for CPU bound programs:

Go is great for I/O bound programs

Deferred Statements

… are bound to function scope and will be called when the function returns or panics:

func foo() {
    file, err := os.Open("pygraz-go.html")
    if err != nil {
        log.Fatalf("os.Open: %v", err)
    }
    defer file.Close()

    // do something with the file [omitted]
}

… can be added dynamically, will execute in LIFO:

func boom() {
    defer fmt.Println("Boom!")
    for i := 1; i <= 10; i++ {
        defer fmt.Println(i)
    }
}

No magic. Go doesn't support constructors, destructors or operator overloading. It's just simpler without.

Example: Counting the number of players

func handleWS(ws *websocket.Conn) {
    atomic.AddInt32(&numPlayers, 1)
    defer atomic.AddInt32(&numPlayers, -1)
    defer ws.Close()

    available <- &Player{Conn: ws}
    // …
}

The sync packages provides basic shared-memory synchronization primitives:

Advice:
Avoid shared mutability for more complex tasks.

Example: Reverting pseudo legal moves

Pseudo legal moves are rare. So we can allow them and revert afterwards if necessary:

func (t *Board) move(a, b pos, undo bool) (valid bool) {
    // check basic movement patterns
    if !canMove(a, b) {
        return false
    }

    // revert experimental or pseudo-legal moves
    backup := *t
    defer func() {
        if undo || !valid {
            *t = backup
        }
    }()

    // apply the move, castling rules, etc. [omitted]
    // modifies the state and might return false

    if check() {
        // the king must not remain in check
        return false
    }

    return true
}

Great Go Projects

vitess
Scaling MySQL databases for the web
doozerd
A completely consistent key value store
gopkgdoc
Displays documentation for Go packages
go.uik
Early prototype of a concurrent GUI library

Go has mainly attracted Python and Ruby programmers (but there are still some Plan9 geeks around).

It's used for many web applications and services, some Google Doodles and other stuff.

Additional Resources

Rob Pike: Public Static Void
Great talk about the motivations behind Go
A Tour of Go
An interactive introduction to Go
Effective Go
A must read for any new Go programmer
Rob Pike: Lexical Scanning in Go
Another good talk about text/template's lexer
The Go Blog
The official Go blog with lots of in-depth articles
research!rsc
Thoughs about computer programming by Russ Cox

Q's and A's
Feel free to ask any questions!