Battleships!

Battleships is a classic game for two players that I remember playing as a child. Each player has their own grid of sea in which they place their ships, which cannot move. Once all ships are placed, each player takes it in turns to guess coordinates for shooting their opponent's grid of sea. They are told if their shot hit an opponent's boat or missed. The first player to sink all of their opponents boats (shoot all of the coordinates occupied by an opponent boat) wins.

This howto would be somewhat long if I included all the code so the boring bits I'm going to miss out. If you've read through the previous howtos then you'll have no problems filling them in.

The code in this Howto, along with the other Howtos are available in the examples repository.

As usual, the first step is to figure out how to model the game data. Each player has their own grid (board) which is 10 by 10. So we have a top game object which has two pointers to each of the player's boards objects. Each player is a client with their own connection, so we can assume that each player first creates their own board, populates it with their own ships, and then writes that board into the references of a game object. From that point on, the two boards will be fixed. This initial setup phase isn't terribly exciting so I'll mainly miss it out. Suffice to say we should be able to create and populate the following two data structures:

package battleships

import (
	"fmt"
	"goshawkdb.io/client"
)

type Game struct {
	objId   client.ObjectRef
	playerA client.ObjectRef
	playerB client.ObjectRef
}

type Player struct {
	conn          *client.Connection
	board         client.ObjectRef
	boats         client.ObjectRef
	opponentBoard client.ObjectRef
}

The Game object tracks the GoshawkDB object representing the overall game. That has two references to the player boards. Each Player will be created by its player/connection. Creating a player creates two unique objects: the board, which will be an empty value but have 100 references to the different cells that make up the grid, and a second object, boats, which contains references to the cells occupied by the player's boats. Placing a boat could then look something like this:

const (
	boardXDim = 10
	boardYDim = 10
)

func (p *Player) PlaceBoat(x, y, boatLength uint, vertical bool) error {
	switch {
	case vertical && y+boatLength >= boardYDim:
		return fmt.Errorf("Illegal position for boat")
	case !vertical && x+boatLength >= boardXDim:
		return fmt.Errorf("Illegal position for boat")
	}
	cellIndices := make([]uint, boatLength)
	if vertical {
		for idx := range cellIndices {
			cellIndices[idx] = y*boardXDim + x + uint(idx)*boardXDim
		}
	} else {
		for idx := range cellIndices {
			cellIndices[idx] = y*boardXDim + x + uint(idx)
		}
	}
	_, _, err := p.conn.RunTransaction(func(txn *client.Txn) (interface{}, error) {
		boardObj, err := txn.GetObject(p.board)
		if err != nil {
			return nil, err
		}
		boardCells, err := boardObj.References()
		if err != nil {
			return nil, err
		}
		boatsObj, err := txn.GetObject(p.boats)
		if err != nil {
			return nil, err
		}
		boatsObjReferences, err := boatsObj.References()
		if err != nil {
			return nil, err
		}
		for _, index := range cellIndices {
			cell := boardCells[index]
			boatsObjReferences = append(boatsObjReferences, cell)
		}
		boatsObj.Set([]byte{}, boatsObjReferences...)
		return nil, nil
	})
	return err
}

There's an obvious mistake here in that cells can be reused for multiple boats so when appending to the boatsObjReferences, we should probably first check to see if that cell is already in there. Exercise for the reader!

The important thing is that the state of the board hasn't changed - the cells themselves don't know if a boat is on it. Instead, the boats know which cells they occupy. This is useful as it means a player can give their board to their opponent and not reveal where their boats are. I certainly remember a lot of cheating on this game when I played it as a child - boats magically managed to move, repeatedly! We certainly can't permit such shenanigans here, so we're going to introduce the idea of a referee.

The referee is a trusted third party who is going to be told where all the boats of both players are. They will then shout out "Hit!" whenever a shot hits a boat. So the referee keeps a list of cells which are occupied by boats and have not yet been hit. When a player shoots a cell, the player just writes a non-empty value to it (literally, the length of the []byte that is the value of the cell is sufficient for our purpose here):

func (p *Player) Shoot(x, y uint) error {
	cellIndex := y*boardXDim + x
	_, _, err := p.conn.RunTransaction(func(txn *client.Txn) (interface{}, error) {
		boardObj, err := txn.GetObject(p.opponentBoard)
		if err != nil {
			return nil, err
		}
		boardCells, err := boardObj.References()
		if err != nil {
			return nil, err
		}
		cell := boardCells[cellIndex]
		if cellValue, err := cell.Value(); err != nil {
			return nil, err
		} else if len(cellValue) != 0 {
			return nil, fmt.Errorf("Illegal shot: already been shot!")
		} else {
			return nil, cell.Set([]byte{0}) // shoot it!
		}
	})
	return err
}

Whilst the referee has un-hit cells, it sits in a loop running a transaction that uses retry to watch for any hits. The referee simply attempts to read from all the cells of both players' boats. If all those cells have an empty value then the referee just issues retry to wait for some shot to hit. When it finds a hit cell, it constructs a new list of cells without the hit cell in it and returns enough information outside of the transaction to be able to then determine which player shot who!

func Referee(conn *client.Connection, playerABoats, playerBBoats []client.ObjectRef) error {
	for len(playerABoats) != 0 && len(playerBBoats) != 0 {
		var boats []client.ObjectRef
		result, _, err := conn.RunTransaction(func(txn *client.Txn) (interface{}, error) {
			for i, cells := range [][]client.ObjectRef{playerABoats, playerBBoats} {
				for j, cell := range cells {
					if cellValue, err := cell.Value(); err != nil {
						return nil, err
					} else if len(cellValue) != 0 {
						// this cell has been shot!
						boats = make([]client.ObjectRef, len(cells)-1)
						copy(boats, cells[:j])
						copy(boats[j:], cells[j+1:])
						return i, nil
					}
				}
			}
			// all the cells we've looked through are unshot.
			return client.Retry, nil
		})
		if err != nil {
			return err
		}
		player := result.(int)
		if player == 0 {
			playerABoats = boats
			fmt.Println("Player B HIT a player A boat!")
		} else {
			playerBBoats = boats
			fmt.Println("Player A HIT a player B boat!")
		}
	}
	if len(playerABoats) == 0 {
		fmt.Println("Player B wins!")
	} else {
		fmt.Println("Player A wins!")
	}
	return nil
}

In this way, the referee uses retry in order to listen for the shots. Now the game as it stands is a curious variant of the original - at least two problems exist: 1) you only get told about hits, not misses, and of course you have no way of knowing how long to wait before silence can be interpreted as a miss; 2) there's not enforcement of turns: you can shoot as rapidly and as often as you'd like!

The most robust way to implement turns is to have two queues to which the players append their targets. The referee then alternates reading from each queue and carries out the shot. The previous howto covered queues in GoshawkDB so the implementation would as explained there.

The act of shooting is how a player discovers the location of their opponent's boats. Therefore when the shot is now carried out by the referee, the referee can mark in the cell itself not just that a shot has been carried out, but whether it hit or missed. The player, after submitting the cell-to-shoot to the referee's queue need just wait for the shot to be recorded in the cell to know the outcome. So this changes some of our code:

type Player struct {
	conn          *client.Connection
	board         client.ObjectRef
	boats         client.ObjectRef
	opponentBoard client.ObjectRef
	shotQueue     *queue.Queue
}

func (p *Player) Shoot(x, y uint) (bool, error) {
	cellIndex := y*boardXDim + x
	result, _, err := p.conn.RunTransaction(func(txn *client.Txn) (interface{}, error) {
		boardObj, err := txn.GetObject(p.opponentBoard)
		if err != nil {
			return nil, err
		}
		boardCells, err := boardObj.References()
		if err != nil {
			return nil, err
		}
		cell := boardCells[cellIndex]
		if cellValue, err := cell.Value(); err != nil {
			return nil, err
		} else if len(cellValue) != 0 {
			return nil, fmt.Errorf("Illegal shot: already been shot!")
		} else {
			return cell, nil
		}
	})
	if err != nil {
		return false, err
	}
	cell := result.(client.ObjectRef)
	if err = p.shotQueue.Append(cell); err != nil {
		return false, err
	}
	result, _, err = p.conn.RunTransaction(func(txn *client.Txn) (interface{}, error) {
		cell, err := txn.GetObject(cell)
		if err != nil {
			return nil, err
		}
		if cellValue, err := cell.Value(); err != nil {
			return nil, err
		} else if len(cellValue) != 0 {
			// shot has been carried out. Referee would have written a 1 if we hit.
			return cellValue[0] == 1, nil
		} else {
			// shot has not happend yet
			return client.Retry, nil
		}
	})
	if err != nil {
		return false, err
	}
	return result.(bool), nil
}

The referee now no longer needs to loop reading from all the boat cells. Instead the referee just alternates between dequeuing of either shot queue, tests to see if the requested cell for shooting is in the appropriate list of boat cells and modifies the cell accordingly. All pretty straight-forward:

type Referee struct {
	conn             *client.Connection
	playerABoats     []client.ObjectRef
	playerBBoats     []client.ObjectRef
	playerAShotQueue *queue.Queue
	playerBShotQueue *queue.Queue
}

func (r *Referee) Run() error {
	turnQ, notTurnQ := r.playerAShotQueue, r.playerBShotQueue
	turnBoats, notTurnBoats := r.playerBBoats, r.playerABoats
	for len(turnBoats) != 0 && len(notTurnBoats) != 0 {
		result, _, err := r.conn.RunTransaction(func(txn *client.Txn) (interface{}, error) {
			cell, err := turnQ.Dequeue()
			if err != nil {
				return nil, err
			}
			shotOutcome := []byte{0}
			for i, boatCell := range turnBoats {
				if cell.ReferencesSameAs(boatCell) {
					shotOutcome[0] = 1 // hit!
					return i, cell.Set(shotOutcome)
				}
			}
			return nil, cell.Set(shotOutcome) // miss
		})
		if err != nil {
			return err
		}
		if result != nil { // remove hit boat cell
			i := result.(int)
			turnBoats = append(turnBoats[:i], turnBoats[i+1:]...)
		}
		// swap turns
		turnBoats, notTurnBoats = notTurnBoats, turnBoats
		turnQ, notTurnQ = notTurnQ, turnQ
	}
	return nil
}

So not a complete implementation of Battleships, but hopefully all the interesting bits have been covered and the game has the right properties: players can't spy on their opponent's boats, they have to take it in turns to fire, and they get to find out whether their shots hit or miss their opponent's boats. This shows how GoshawkDB can be used not just as a data store but as a coordination platform for communication between different clients - all possible because of the support of retry.