Leandro Facchinetti

Playing the Game with PLT Redex

Peg Solitaire Rules

Peg Solitaire is a single-player board game that starts with the following board:

Initial Board

    ● ● ●
    ● ● ●
● ● ● ● ● ● ●
● ● ● ○ ● ● ●
● ● ● ● ● ● ●
    ● ● ●
    ● ● ●


●  Peg
○  Space

With each move, a peg can jump over one of its four immediate neighbors and land on a space. The neighbor peg that was jumped over is removed from the board. For example, the following are the four possible starting moves:

Examples of Valid Moves (Starting Moves)

    ● ● ●             ● ● ●
    ●  ●             ● ○ ●
● ● ●  ● ● ●     ● ● ●  ● ● ●
● ● ● ○ ● ● ●    ● ● ●  ● ● ●
● ● ● ● ● ● ●     ● ● ● ● ● ● ●
    ● ● ●             ● ● ●
    ● ● ●             ● ● ●

    ● ● ●             ● ● ●
    ● ● ●             ● ● ●
● ● ● ● ● ● ●     ● ● ● ● ● ● ●
● ● ● ○    ● ● ●   ○ ●
● ● ● ● ● ● ●     ● ● ● ● ● ● ●
    ● ● ●             ● ● ●
    ● ● ●             ● ● ●

    ● ● ●             ● ● ●
    ● ● ●             ● ● ●
● ● ● ● ● ● ●     ● ● ● ● ● ● ●
● ● ● ○ ● ● ●    ● ● ●  ● ● ●
● ● ●  ● ● ●     ● ● ●  ● ● ●
    ●  ●             ● ○ ●
    ● ● ●             ● ● ●

    ● ● ●             ● ● ●
    ● ● ●             ● ● ●
● ● ● ● ● ● ●     ● ● ● ● ● ● ●
●   ○ ● ● ●    ● ○   ● ● ●
● ● ● ● ● ● ●     ● ● ● ● ● ● ●
    ● ● ●             ● ● ●
    ● ● ●             ● ● ●


 jumps over 

The following are examples of invalid moves:

The goal of Peg Solitaire is to leave a single peg on the board, for example:

Example of Winning Board

    ○ ○ ○
    ○ ○ ○
○ ○ ○ ○ ○ ○ ○
○ ○ ○ ● ○ ○ ○
○ ○ ○ ○ ○ ○ ○
    ○ ○ ○
    ○ ○ ○

The following is an example of a lost game in which two pegs remain on the board, but they are not neighbors, so there are no moves left:

Example of Losing Board

    ○ ○ ○
    ○ ○ ○
○ ○ ○ ● ○ ○ ○
○ ○ ○ ○ ○ ○ ○
○ ○ ○ ○ ○ ● ○
    ○ ○ ○
    ○ ○ ○

Prototype

Our first implementation is the bare minimum to play the game. Over the course of the next sections we revisit the corners we cut and dive deeper into each topic.

Setup

We start by requiring PLT Redex:

introduction.rkt

#lang racket
(require redex)

Language and Terms

Most PLT Redex forms work over languages, so we define a language for Peg Solitaire:

(define-language peg-solitaire)

The peg-solitaire language is analog to a programming language, for example, Racket or Ruby. Programs and program fragments in these programming languages are called terms, for example, the following are terms in Racket:

Example of Term: Complete Program

(define favorite-number 5)

Example of Term: Fragment of Program Above

5

In the peg-solitaire language, however, terms are not programs and program fragments, but Peg Solitaire entities, for example, pegs and boards. From PLT Redex’s perspective programs are data structures, and we abuse this notion to represent Peg Solitaire entities. The definition of the peg-solitaire language above does not specify the language shape—it does not define which terms represent which Peg Solitaire entities—but it suffices for our prototype (we revisit it in a later section).

Terms in PLT Redex can be any S-expression, and we represent a Peg Solitaire board with a list of lists of positions, each of which may be symbols representing pegs, spaces, and paddings:

(define-term initial-board
  ([· ·    · ·]
   [· ·    · ·]
   [      ]
   [      ]
   [      ]
   [· ·    · ·]
   [· ·    · ·]))


;; ●  Peg
;; ○  Space
;; ·  Padding

PLT Redex does not check that the initial-board is in the peg-solitaire language, so the listing above works despite the definition of the peg-solitaire language not specifying what constitutes a board.

Moves

To model how a player moves pegs on the board, we use a PLT Redex form called reduction-relation to define the reduction relation. A reduction relation is similar to a function, except that it is nondeterministic, possibly returning multiple outputs. We choose to define as a reduction relation instead of a regular function because there might be multiple moves for a given input board. We start to define as a reduction relation that operates on the peg-solitaire language:

(define
  
  (reduction-relation
   peg-solitaire
   ___))

We then provide one clause for each kind of possible move. For example, for a peg to jump over its right neighbor, we must find a sequence ● ● ○ on the board, and that sequence turns into ○ ○ ● after the move, while the rest of the board remains the same. We write this as a reduction-relation as follows:

(--> (any_1
      ...
      [any_2 ...    any_3 ...]
      any_4
      ...)
     (any_1
      ...
      [any_2 ...    any_3 ...]
      any_4
      ...)
     "→")

In the listing above, the --> form represents one kind of possible move. The first sub-form is a pattern against which the input board is matched, the second sub-form is the template with which to generate the output, and the third sub-form is the name of this kind of move, . The several any_<n> preserve the rest of the board around the moved pegs.

We define the other kinds of moves similarly. The following is the complete definition of :

(define
  
  (reduction-relation
   peg-solitaire

   (--> (any_1
         ...
         [any_2 ...    any_3 ...]
         any_4
         ...)
        (any_1
         ...
         [any_2 ...    any_3 ...]
         any_4
         ...)
        "→")

   (--> (any_1
         ...
         [any_2 ...    any_3 ...]
         any_4
         ...)
        (any_1
         ...
         [any_2 ...    any_3 ...]
         any_4
         ...)
        "←")

   (--> (any_1
         ...
         [any_2 ..._n  any_3 ...]
         [any_4 ..._n  any_5 ...]
         [any_6 ..._n  any_7 ...]
         any_8
         ...)
        (any_1
         ...
         [any_2 ...    any_3 ...]
         [any_4 ...    any_5 ...]
         [any_6 ...    any_7 ...]
         any_8
         ...)
        "↓")

   (--> (any_1
         ...
         [any_2 ..._n  any_3 ...]
         [any_4 ..._n  any_5 ...]
         [any_6 ..._n  any_7 ...]
         any_8
         ...)
        (any_1
         ...
         [any_2 ...    any_3 ...]
         [any_4 ...    any_5 ...]
         [any_6 ...    any_7 ...]
         any_8
         ...)
        "↑")))

Playing

PLT Redex features visualization tools, including a stepper, which we use to play Peg Solitaire:

(stepper  (term initial-board))

Playing Peg Solitaire with PLT Redex’s stepper. The main pane shows the board over time, with pegs that changed on the last move highlighted. The bottom pane shows in purple the path we have taken, and white nodes are alternative paths with different moves, for example, jumping right instead of left.


On the following sections we revisit each step of modeling Peg Solitaire in PLT Redex in more detail, starting with terms.