38 Two board games

We have implemented two board games, Explode (Figure 98) and Othello (Figure 99) using Fudgets.

The two games use the same underlying combinators for implementing the board. The first is a button that can display changing graphics:

boardButtonF ::  (ColorGen bgcolor, Graphic gfx) =>
                 bgcolor -> Size -> F gfx Click
boardButtonF bg size =
  buttonF'' (setBgColor bg) (g (blankD size)) >=^< Left . setLabel . g
where buttonF'' is the dynamically customisable (see Section 30.3) version of buttonF and setLabel is a customiser that changes the button label.

The second combinator is boardF,

type Coord = (Int,Int)

boardF :: Coord -> (Coord -> F a b) -> F (Coord,a) (Coord,b)
boardF (w,h) squareF =
  placerF (matrixP w) $
  listF [((x,y),sqF (x,y)) | y<-[0..h-1],x<-[0..w-1]]
which, given the size of the board and a function from the coordinates of a square to a fudget implementing that square, creates a parallel composition of square fudgets with the appropriate layout. The square fudgets are addressed with their coordinates.

Figure 98. The Explode game.

Figure 99. The Othello game.

38.1 The Explode Game

Before the 1995 GUI Festival in Glasgow, a workshop on graphical user-interface toolkits and functional programming [Car95], a number of programming challenges were distributed to the participants. One of the challenges was to implement the Explode game.

In the Explode game, two players take turns placing stones, or atoms, in the squares of a board. A player can not place atoms in a square that already contains atoms from the opponent. When a square is full, that is, contains as many atoms as it has neighbours, it explodes, sending one atom to each neighbour. All atoms of the invaded square change color to the invading atom's color. Invaded squares may become full and explode in turn. When the board has settled, a new move can be entered. When the board starts to get full of atoms, placing a new atom may cause an infinite chain reaction. When this happens, the game is over and the player who caused it is the winner.

38.1.1 The Fudgets implementation of the Explode game

The Fudgets implementation of the Explode game was done as shown in Figure 100.
main = fudlogue (shellF "Explode" explodeBoardF)

explodeBoardF =
    loopF (absF routeSP >==< boardF boardSize boardSize atomsSquareF)
    routeSP = concatMapAccumlSP route White
    route side (src,msg) =
      case msg of
        ClickedWhileEmpty -> (otherSide side, [(src,side)])
        ClickedWithColor side' ->
          if side'==side
          then (otherSide side, [(src,side)])
          else (side, []) -- illegal move
        Explode dsts side' -> (side, [(dst,side')|dst<-dsts])

    atomsSquareF :: Coord -> F AtomColor (SquareEvent Coord)
    atomsSquareF (x,y) =
        loopThroughRightF (absF ctrlSP) atomsButtonF
        ctrlSP = concatMapAccumlSP ctrl (0,Nothing)
        ctrl s@(oldcnt,oldside) msg =
          case msg of
            Left Click -> (s,[Right (case oldside of
                                       Just side  -> ClickedWithColor side
                                       Nothing    -> ClickedWhileEmpty)])
            Right side ->
              let cnt=oldcnt+1
              in if cnt>=size
                 then become (cnt-size) side (explodemsgs side)
                 else become cnt side []

        become cnt side msgs = ((cnt,optside),Left (cnt,side):msgs)
          where optside = if cnt==0 then Nothing else Just side
        size = length neighbours
        explodemsgs = (:[]) . Right . Explode neighbours
        neighbours = filter inside2d [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
        inside2d (x,y) = inside x && inside y
        inside x = 0<=x && x<boardSize

        atomsButtonF :: F (NumberOfAtoms,AtomColor) Click
        atomsButtonF = boardButtonF bgColor sqsize >=^< drawAtoms

        drawAtoms (count,color) = ... -- 20 lines

Figure 100. Fudgets implementation of the Explode game.


38.1.2 A comparison of the Fudgets and Gadgets versions of the Exlode Game

The submitters of the Explode challenge also provided a solution using Gadgets (see Section 41.3.1). Their solution (see section 6 in [NR95]) is similar to ours in that the effects of the users' moves are computed by message passing between processes representing the squares of the board. In both solutions, there is a separate referee process that, for example, keeps track of whose turn it is to move.

In the Fudgets solution, the squares are in effect connected to all other squares, whereas in the Gadgets solution, each square process is connected through wires only to its neighbours. As noted in [NR95], combining fudgets to achieve exactly this connectivity would be difficult, and it would probably also be difficult to add new processes to such a solution.

As described above, in the current Fudgets solution, each square fudget knows its coordinates and computes the coordinates of its neighbours. It would of course be possible to parameterise the square fudgets by an abstract representation of the neighbours instead,

atomsSquareF :: [address] -> F AtomColor (SquareEvent address)
and let routeSP compute the concrete addresses of the neighbours. This perhaps makes the communication pattern more visible in the program text and prevents errors in the implementation of atomsSquareF from breaking the pattern.

Since the Gadgets system uses indeterministic process scheduling, it is necessary to explicitly keep track of when an explosion is in progress and when the board is stable, since moves are allowed to be entered only when the board is stable. The implementation of Fudgets is deterministic and internal communication has priority over external communication, so user input is automatically queued until an explosion has subsided.

38.2 The Othello Game

The fudgets version of the game Othello allows a human player to play against the computer or another human player. It was implemented by reusing an existing implementation from 1990 with a TTY-based user interface. 388 of 584 lines were reused without changes. About 100 new lines were added for the new graphical user interface. This demonstrates that the separation of user-interface-specific code and application-specific code is good.

In the implementation of the Explode game, we used a distributed solution: the work of computing the effects of the users' moves is handled almost entirely by the square fudgets. In the implementation of Othello, we have taken the opposite approach: the board fudget only displays the board and receives user input. The checking of the validity of a move and computation of its effect is handled by a stream processor attached in the typical way with the loopThroughRightF combinator (see Section 18.2). The structure of the program is:

main = fudlogue (shellF "Othello" ottoF)

ottoF = 
  >==< loopThroughRightF (absF newGameSP) ottoBoardF
  >==< buttonF "New Game"

ottoBoardF :: F BoardReq Coord
ottoBoardF = ...

newGameSP = playSP (reptree moves startpos)

playSP :: GameTree -> SP (Either Coord Click) (Either BoardReq String)
playSP current_position = ...
The function reptree (lazily) computes a game tree which has startpos as the root node and where the children of a node are obtained by applying the function moves to it.

The stream processor playSP checks the current position for whose turn it is to play, and then either waits for the user to enter a move or computes a good move for the computer using standard alfa-beta game-tree search.