Chess Anyone?

Computer chess games are available via chess game applications that can be downloaded to a machine (e.g. Chess Titans) as well as interactive chess games found on the Internet; simply searching for “chess game” will produce a list of websites providing this service. These applications and websites let you play against either a live opponent or the machine. With these games a chess board is presented in the starting position and we choose whether to play white or black. Moves are recorded as a sequence of entries by each player and are reflected in the arrangement of pieces on the board.

The chess game move recording system currently in use regards the chess board as a set of 64 named squares with columns from left to right marked as a through h and rows from bottom to top marked as 1 through 8, as shown in Figure 25-1.

Figure 25-1. Identification of squares on a chess board

Each square in Figure 25-1 is identified by its column and row coordinates. For example, the lower right square is identified as h1 (column h, row 1). A game begins with the white pieces arranged as described below, showing the piece abbreviations in parenthesis:

• King (K) at e1

• Queen (Q) at d1

• Bishops (B) at c1 and f1

• Knights (N) at b1 and g1

• Rooks (R) at a1 and h1

• Pawns occupying all the row 2 squares

The black pieces are arranged in the same columns as the white pieces but occupy rows 7 and 8.

The format for representing the series of moves is simply to indicate the piece to be moved and the destination square, except for pawns, which simply indicate the destination square. An x following the piece abbreviation is used to indicate a piece is taken, and ch following the destination square indicates that the move has placed the opponents king in check. The move sheet shown in Table 25-1 provides an example of moves made during a chess game, with the corresponding description of the moves shown in Table 25-2.

The move sheet shown above describes the opening moves of what has come to be known as The Immortal Game, a famous game played in London in 1851 between Adolf Anderssen and Lionel Kieseritsky. For the computer to represent this series of moves on the displayed chess board, it would need to clear the square the moving piece occupies before the move and then apply the icon of the moving piece at the destination square.

Table 25-3 shows a variation of the chess move sheet describing the same opening moves of The Immortal Game, but this time shows only a single move of a piece per row. The indication of how the chess board display would change with each move is shown in Table 25-4.

The UML class diagram shown in Figure 25-2 illustrates how we might construct the objects to handle the chess board, the chess game, and the moves representing The Immortal Game.

Figure 25-2. UML class diagram for the computerized chess game design

In this arrangement, there is a client entity that uses the class immortal_game, a class in which the moves of the immortal game have been captured for replay. Class immortal_game is designed as a singleton instance, providing public behavior play that can be invoked by the client to repeat the moves of the immortal game. It is also composed of a private attribute game, a reference to an instance of class chess_game. Class chess_game provides public behaviors new_game and move. It also has private attributes white_moves, a table of type string; black_moves, also a table of type string; next_mover, a flag to indicate the next mover (white or black); and board, a reference to an instance of class chess_board. Accordingly, the instance of chess_game is composed of an instance of chess_board. Class chess_board provides public behaviors apply_player_move and display in addition to private attributes to represent each of the 64 squares of the chess board.

The ABAP-style pseudocode in Listing 25-1 shows how these classes interact with each other to simulate playing The Immortal Game.

Listing 25-1. Pseudocode for Interaction of Classes Described in Figure 25-2

report.
class chess_board definition.
  public section.
    methods      : display
                 , apply_player_move
                     importing movement
                       type string
                 .
  private section.
    data         : square_a1      type square value white_rook_icon
                 , square_b1      type square value white_knight_icon
                   ...
                 , square_g8      type square value black_knight_icon
                 , square_h8      type square value black_rook_icon
                 .
endclass.
class chess_board implementation.
  method display.
    display all 64 squares of chess board.
  endmethod.
  method apply_player_move.
    determine moving piece icon.
    determine source square.
    determine target square.
    clear source square.
    target square                 = moving piece icon.
  endmethod.
endclass.

class chess_game definition.
  public section.
    constants    : white          type char1 value 'W'
                 , black          type char1 value 'B'
                 .
    methods      : new_game
                 , move
                     importing
                       movement
                         type string
                 .
  private section.
    data         : board          type ref to chess_board
                 , white_moves    type standard table of string
                 , black_moves    type standard table of string
                 , next_mover     type char1
                 .
endclass.
class chess_game implementation.
  method new_game.
    clear: white_moves, black_moves.
    next_mover                    = white.
    create object board.
    board->display( ).
  endmethod                                          .
  method move.
    if next_mover                 eq white.
      append movement             to white_moves.
      next_mover                  = black.
    else.
      append movement             to black_moves.
      next_mover                  = white.
    endif.
    board->apply_player_move( movement ).
    board->display( ).
  endmethod.
endclass.

class immortal_game definition.
  public section.
    class-data   : singleton      type ref to immortal_game read-only.
    class-methods: class_constructor.
    methods      : constructor
                 , play
                 .
  private section.
    data         : game           type ref to chess_game.
endclass.
class immortal_game implementation.
  method class_constructor.
    create object immortal_game=>singleton.
  endmethod.
  method constructor                                          .
    create object me->game.
  endmethod.
  method play.
    me->game->new_game( ).
    me->game->move( `e4` ).          " 1   e4    ...
    me->game->move( `e5` ).          " 1   ...   e5
    me->game->move( `f4` ).          " 2   f4    ...
    me->game->move( `exf4` ).        " 2   ...   exf4
    me->game->move( `Bc4` ).         " 3   Bc4   ...
    me->game->move( `Qh4` ).         " 3   ...   Qh4ch
    me->game->move( `Kf1` ).         " 4   Kf1   ...
    me->game->move( `b5` ).          " 4   ...   b5
    me->game->move( `Bxb5` ).        " 5   Bxb5  ...
    me->game->move( `Nf6` ).         " 5   ...   Nf6
    me->game->move( `Nf3` ).         " 6   Nf3   ...
    me->game->move( `Qh6` ).         " 6   ...   Qh6
      ...
  endmethod.
endclass.
start-of-selection.
  immortal_game=>singleton->play( ).

Player’s Remorse

One feature found with the chess games where the machine can be our opponent is the ability to undo a series of moves. Such backtracking is usually sought after the machine makes a move placing our pieces in a compromising position, and, once the weak position is revealed, enables us to reconsider and redo one or more of our previous moves. A button is usually provided for this capability, called “Previous move” or “Undo,” and clicking it once undoes the most recent move. Pressing the button repeatedly continues this process until you reach the starting position of the game.

One of the techniques by which the corresponding display can be changed when the user presses the Undo button is to clear the chess board display back to the starting position for a new game and then to apply each of the moves recorded in the move sheet in succession until reaching the point prior to the most recent move. An alternative to this brute force design is to take a snapshot of the board arrangement after each move and, when an undo is requested, simply retrieve the most recent snapshot and rearrange the board accordingly. The first technique could be regarded as process intensive, the second as storage intensive; that is, the first technique requires the consumption of CPU time to process all the moves from the start of the game in its quest to reset the board to the corresponding display, whereas the second technique requires the consumption of storage for as many snapshots of the board as there are moves being made as the game progresses. The first technique might result in slow response time while the display is being rebuilt move-by-move, while the second technique will cause storage to be consumed for each snapshot whether or not a specific snapshot is required later. Accordingly, any technique chosen to reset the chess board will have its pros and cons.

Forget-Me-Not

The Memento design pattern facilitates the snapshot technique described above. Specific arrangements of pieces on the chess board are recorded so that the board may be reset to a previous position.

The Memento design pattern is categorized by GoF with a behavioral purpose and an object scope. The intent behind this design pattern is the following:

• Without violating encapsulation, capture and externalize an object's internal state so that the object can be restored to this state later. ¹

Memento makes use of these participants² working in collaboration with each other:

1. Memento: Stores the internal state of the Originator object. The memento may store as much or as little of the originator's internal state as necessary at its originator's discretion. Protects against access by objects other than the originator. Mementos have effectively two interfaces. Caretaker sees a narrow interface to the memento; it can only pass the memento to other objects. Originator, in contrast, sees a wide interface , one that lets it access all the data necessary to restore itself to its previous state. Ideally, only the originator that produced the memento is permitted to access the memento's internal state.

2. Originator : Creates a memento containing a snapshot of its current internal state. Uses the memento to restore its internal state.

3. Caretaker : Is responsible for the memento's safekeeping. Never operates on or examines the contents of a memento.

In the chess game scenario, class chess_board in Listing 25-1 plays the role of the Originator participant. It is the class whose internal state holds the information about how the pieces are arranged on the board at any moment; snapshots of these arrangements need to be made available to reset the pieces to some previous arrangement. It both creates the mementos recording its internal state with each move and uses one or more of these mementos to restore its internal state, effectively resetting the chess board arrangement to represent a previous point in the game.

Class chess_board_memento plays the role of the Memento participant. It holds the arrangement of the chess board at a given point in the game.

Class chess_game plays the role of the Caretaker participant, requesting chess_board to create an instance of a chess_board_memento that chess_game retains in its internal tables of white and black mementos.

The UML class diagram for the Memento design pattern is shown in Figure 25-3.

Figure 25-3. UML class diagram for the Memento design pattern

Here we see the originator class providing behaviors createMemento, to create a memento using its own internal state, and setMemento, to reset its internal state using a memento provided through the signature of the behavior. Some external entity requests the originator to create a memento, and when later it is determined that the originator should be set to some previous internal state, again an external entity provides one of the mementos previously created by the originator in requesting the originator reset its own internal state.

The memento class merely facilitates holding a snapshot of the internal state of the originator, providing behaviors getState and setState for getting and setting the state, respectively.

The caretaker class is shown retaining references to the memento instances; that is, caretaker “has a” set of references to mementos. In many cases, the caretaker also is the entity that requests the originator to create the mementos it retains as well as the entity requesting the originator to reset its internal state using one of those mementos.

Notice that the originator class both creates and uses the mementos.

The UML class diagram shown in Figure 25-4 is the same as shown in Figure 25-2 for The Immortal Game but altered to illustrate the use of the memento design pattern, showing the new attributes and methods to be added to existing classes as well as a new class with its relationship to the others; all differences with the UML diagram in Figure 25-2 are highlighted.

Figure 25-4. UML class diagram for the Memento design pattern applied to the chess game scenario

In this arrangement, the new chess_board_memento class plays the role of the Memento participant, class chess_board class plays the role of the Originator participant, and the chess_game class plays the role of the Caretaker participant. Prior to applying a move, the move method of the chess_game instance now requests the chess_board instance, via method create_memento, to create an instance of chess_board_memento which chess_game alternately will place into its white_mementos or black_mementos table for safe keeping. Upon a request to reverse a chess move, new method undo_move of instance chess_game invokes its private method reset_board, which now will find the appropriate chess_board_memento in its white_mementos and black_mementos tables and request the chess_board instance, via method reset_using_memento, to reset the chess board, after which method undo_move will alter its attributes tracking white and black moves as well as white and black mementos accordingly to discard the undone move and its corresponding memento.

Here we see that the constructor of the chess_board_memento instance provides the capability for its private attribute values to be set to their matching attributes in the chess_board class; that is, when the chess_board instance creates a chess_board_memento instance, it will provide the values of all its 64 private attributes as parameters on the instance constructor, which the constructor will then use to initialize the values of the private attributes of its own instance.

Memento in ABAP

The following ABAP-style pseudocode shows how these modified classes interact with each other to simulate playing The Immortal Game, this time with the ability to undo moves and replay them again. Listing 25-2 shows a new class required to facilitate using the Memento design pattern.

Listing 25-2. Class chess_board_memento

class chess_board_memento definition.
  public section.
    methods      : constructor
                     importing square_a1 type square
                               square_b1 type square
                                 ...
                               square_g8 type square
                               square_h8 type square
                 , get_board_settings
                     exporting square_a1 type square
                               square_b1 type square
                                 ...
                               square_g8 type square
                               square_h8 type square
                 .
  private section.
    data         : square_a1      type square
                 , square_b1      type square
                   ...
                 , square_g8      type square
                 , square_h8      type square
                 .
endclass.
class chess_board_memento implementation.
  method constructor.
    me->square_a1                 = square_a1.
    me->square_b1                 = square_b1.
      ...
    me->square_g8                 = square_g8.
    me->square_h8                 = square_h8.
  endmethod.
  method get_board_settings.
    square_a1                     = me->square_a1.
    square_b1                     = me->square_b1.
      ...
    square_g8                     = me->square_g8.
    square_h8                     = me->square_h8.
  endmethod.
endclass.

The chess_board_memento class , shown in Listing 25-2, plays the role of the Memento participant. Notice that its sole purpose is to retain the image of all 64 squares on a chess board through its constructor method and then return this information to a caller through the get_board_settings method. Listing 25-3 shows class chess_board, with the differences from Listing 25-1 highlighted.

Listing 25-3. Class chess_board, with Differences from Listing 25-1 Highlighted

class chess_board definition.
  public section.
    methods      : display
                 , apply_player_move
                     importing movement
                       type string
                 , create_memento
                     returning value(memento)
                       type ref to chess_board_memento
                 , reset_using_memento
                     importing memento
                       type ref to chess_board_memento
                 .
  private section.
    data         : square_a1      type square value white_rook_icon
                 , square_b1      type square value white_knight_icon
                   ...
                 , square_g8      type square value black_knight_icon
                 , square_h8      type square value black_rook_icon
                 .
endclass.
class chess_board implementation.
  method display.
    display all 64 squares of chess board.
  endmethod.
  method apply_player_move.
    determine moving piece icon.
    determine source square.
    determine target square.
    clear source square.
    target square                 = moving piece icon.
  endmethod.
  method create_memento.
    create object memento
      exporting square_a1         = me->square_a1
                square_b1         = me->square_b1
                  ...
                square_g8         = me->square_g8
                square_h8         = me->square_h8.
  endmethod.
  method reset_using_memento.
    call method chess_board_memento->get_board_settings
      importing square_a1         = me->square_a1
                square_b1         = me->square_b1
                  ...
                square_g8         = me->square_g8
                square_h8         = me->square_h8.
  endmethod.
endclass.

The chess_board class, shown in Listing 25-3, plays the role of the Originator participant. It has two additional methods to facilitate the Memento design pattern. Its create_memento method creates an instance of a chess_board_memento, representing its current internal state, which is passed back to the caller, and its reset_using_memento method resets its internal state using the instance of a chess_board_memento provided by the caller. Notice that the chess_board class is not retaining any information about the mementos it creates. Listing 25-4 shows class chess_game, with its differences from Listing 25-1 highlighted.

Listing 25-4. Class chess_game, with Differences from Listing 25-1 Highlighted

class chess_game definition.
  public section.
    constants    : white          type char1 value 'W'
                 , black          type char1 value 'B'
                 .
    methods      : new_game
                 , move
                     importing
                       movement
                         type string
                 , undo_move
                 .
  private section.
    data         : board          type ref to chess_board
                 , white_moves    type standard table of string
                 , black_moves    type standard table of string
                 , next_mover     type char1
                 , white_mementos type standard table
                                    of chess_board_memento
                 , black_mementos type standard table
                                    of chess_board_memento
                 .
    methods      : reset_board.
endclass.
class chess_game implementation.
  method new_game.
    clear: white_moves, black_moves, white_mementos, black_mementos.
    next_mover                    = white.
    create object board.
    board->display( ).
  endmethod                                          .
  method move.
    data         : board_memento  type ref to chess_board_memento.

    board_memento = board->create_memento( ).
    if next_mover                 eq white.
      append board_memento        to white_mementos.
      append movement             to white_moves.
      next_mover                  = black.
    else.
      append board_memento        to black_mementos.
      append movement             to black_moves.
      next_mover                  = white.
    endif.
    board->apply_player_move( movement ).
    board->display( ).
  endmethod.
  method undo_move.
    reset_board( ).
    if next_mover                 eq white.
      next_mover                  = black.
      delete final row from: black_moves, black_mementos.
    else.
      next_mover                  = white.
      delete final row from: white_moves, white_mementos.
    endif.
    board->display( ).
  endmethod.
  method reset_board.
    data         : board_memento  type ref to chess_board_memento.
    if next_mover                 eq white.
      read final row of black_mementos into board_mementos.
    else.
      read final row of white_mementos into board_mementos.
    endif.
    board->reset_using_memento( board_memento ).
  endmethod.
endclass.

The chess_game class, shown in Listing 25-4, plays the role of the Caretaker participant. It has additional attributes and methods to facilitate maintaining a table of memento objects with each new move as well as resetting the board to a previous state. Notice that this class merely requests for and keeps the memento components with each forward move; with a request for a backward move, it simply identifies the most recent memento and then issues a call to its instance of chess_board to reset itself using this memento.

As shown in Listing 25-5, the report has been changed to invoke the new undo_move method of the chess_game class to undo moves 5 and 6 of the Immortal Game and to replay them again, with the differences from Listing 25-1 highlighted.

Listing 25-5. Class immortal_game, with Differences from Listing 25-1 Highlighted

class immortal_game definition.
  public section.
    class-data   : singleton      type ref to immortal_game read-only.
    class-methods: class_constructor.
    methods      : constructor
                 , play
                 .
  private section.
    data         : game           type ref to chess_game.
endclass.
class immortal_game implementation.
  method class_constructor.
    create object immortal_game=>singleton.
  endmethod.
  method constructor.
    create object me->game.
  endmethod.
  method play.
    me->game->new_game( ).
    me->game->move( `e4` ).          " 1   e4    ...
    me->game->move( `e5` ).          " 1   ...   e5
    me->game->move( `f4` ).          " 2   f4    ...
    me->game->move( `exf4` ).        " 2   ...   exf4
    me->game->move( `Bc4` ).         " 3   Bc4   ...
    me->game->move( `Qh4` ).         " 3   ...   Qh4ch
    me->game->move( `Kf1` ).         " 4   Kf1   ...
    me->game->move( `b5` ).          " 4   ...   b5
    me->game->move( `Bxb5` ).        " 5   Bxb5  ...
    me->game->move( `Nf6` ).         " 5   ...   Nf6
    me->game->move( `Nf3` ).         " 6   Nf3   ...
    me->game->move( `Qh6` ).         " 6   ...   Qh6
    " Undo moves 5 and 6 and play them over again:
    me->game->undo_move( ). " reset to 6   Nf3   ...
    me->game->undo_move( ). " reset to 5   ...   Nf6
    me->game->undo_move( ). " reset to 5   Bxb5  ...
    me->game->undo_move( ). " reset to 4   ...   b5
    me->game->move( `Bxb5` ).        " 5   Bxb5  ...
    me->game->move( `Nf6` ).         " 5   ...   Nf6
    me->game->move( `Nf3` ).         " 6   Nf3   ...
    me->game->move( `Qh6` ).         " 6   ...   Qh6
      ...
  endmethod.
endclass.

Plugging a Security Exposure

Although we now have a working memento capability at our disposal, we’re not quite finished. The current relationship between the classes exposes the possibility that any entity could create an instance of a memento, using any values it might choose to provide to represent the internal state of the originator , and then use that bogus memento to request the originator to reset its state accordingly.

To plug this security exposure, we need a way to indicate that memento instances can be created only by the originator participant. At the moment, we have a memento class enabling instantiation by any other entity.

Restricting creation of memento objects to only certain other types of classes can be achieved by using class friendship , whereby a class indicates the names of those classes it considers its friends. Declaring the memento class to offer friendship only to its corresponding originator class in addition to declaring all memento members in the private section and including the create private qualifier on its class definition will restrict the use of mementos only to its originators . Indeed, a portion of the description of the Memento participant states

• Ideally, only the originator that produced the memento would be permitted to access the memento's internal state.³

Recall that in the section on friendship it was revealed that friendship has the undesirable effect of breaking encapsulation. Whereas this is generally true with friendship offered between classes, it is not applicable to the Memento design pattern simply because the memento itself exists only in service of the originator. Specifically, the originator creates the memento for the very purpose of holding its internal state, so there is no reason for the originator to make direct changes to the attribute values of the memento since it provided those values in the first place. Not only that, but after creating it the originator typically does not retain a reference to an instance of a memento through which it could make such changes. It is the caretaker that keeps the memento reference safely secured until it is needed later, and the caretaker, not having been offered friendship by the memento, has no access to those members, all of which now are marked privately visible .

Listing 25-6 shows how we would alter the definition of the memento class to insure that only originators can create it and have access to its members, with the differences from Listing 25-2 highlighted.

Listing 25-6. Definition of Class chess_board_memento, with Differences from Listing 25-2 Highlighted

class chess_board definition                                      deferred                                                                                                                .                
class chess_board_memento definition create private friends chess_board.
  private section.
    methods      : constructor
                     importing square_a1 type square
                               square_b1 type square
                                 ...
                               square_g8 type square
                               square_h8 type square
                 , get_board_settings
                     exporting square_a1 type square
                               square_b1 type square
                                 ...
                               square_g8 type square
                               square_h8 type square
                 .
  private section.
    data         : square_a1      type square
                 , square_b1      type square
                   ...
                 , square_g8      type square
                 , square_h8      type square
                 .
endclass.

With these changes, no entities other than chess_board can create an instance of a chess_board_memento, and even if some other entity, such as an instance of chess_game, were able to get a reference to a chess_board_memento instance, it could not access any of its attributes or invoke any of its methods, since all of them are defined in the private section.

In Listing 25-6 the class statement of the chess_board_memento class is preceded with a class statement deferring definition of the chess_board class. This is necessary only with local definitions of classes when the definition component of a class refers to a class that has not yet been encountered by the compiler; the chess_board_memento class refers in its friends clause to the yet-to-be-encountered chess_board class.

Summary

In this chapter, we learned a way to retain the internal state of an instance in an external component that can be used to reset the internal state at a later time, all while enabling us to adhere to the object-oriented principle of encapsulation. We also learned that there are cases where we might want to restrict only to certain types of classes the ability to create memento objects, and that class friendship can facilitate this for us. Although friendship is a technique that typically results in breaking encapsulation, it can be ignored with the Memento design pattern due to the fact that the memento object is created by and exists solely to service the class it designates as its friend.

Memento Exercises

Refer to Chapter 22 of the functional and technical requirements documentation (see Appendix B) for the accompanying ABAP exercise programs associated with this chapter. Take a break from reading the book at this point to reinforce what we have read by changing and executing the corresponding exercise programs. The exercise programs associated with this chapter are those in the 315 series: ZOOT315A through ZOOT315F.