TweetFollow Us on Twitter

Assoc Arrays
Volume Number:7
Issue Number:4
Column Tag:MacOOPs!

Associative Arrays

By Allen Stenger. Gardena, CA

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

Associative Arrays

Associative arrays are arrays that are indexed by something other than integers. This article shows a board-game--playing program that indexes an array by the current board position to get the next move.

Several languages have associative arrays built into them, under various names: SNOBOL4 (tables), LISP (association lists), REXX (no special name - all arrays can be indexed by numbers or strings or both), Smalltalk (Dictionaries), and AWK (associative arrays). Most of these allow indexing only by strings, although Smalltalk allows any type or combination of types of objects. (Hardware implementations of associative arrays are called associative memories or content-addressable memories. For example, cache memories usually use a small associative memory to determine whether the desired address is in the cache, and if so, where. The associative memory uses the desired address as the key and the cache location as the data.)

The game we will implement is Hexapawn, which was invented by Martin Gardner in 1962 to demonstrate machine learning. Back in 1962 few of his readers could be expected to have access to electronic computers, so he provided an implementation as a mechanical computer. We will follow the best traditions of object-oriented programming by re-implementing his machine as a computer program.

Hexapawn is a very restricted version of chess. It is played on a 3x3 chessboard with six pawns (hence the name Hexapawn), three pawns on each side. As in chess, a pawn can move ahead one space if the space is free, and can capture an enemy pawn diagonally. The first player to advance to the other side of the board wins. Unlike chess, if a player is blocked, he loses. Therefore there are no draws in Hexapawn.

It happens that Black has a winning strategy in Hexapawn, i.e. Black can always win if he plays correctly. In Gardner’s implementation the machine always plays Black, and although it starts out with no knowledge it eventually learns enough to become unbeatable.

Gardner’s machine is implemented as a set of 24 matchboxes, one for each possible board position when it is Black’s move. Each matchbox has pasted on it a drawing showing this board position, as well as all possible moves from that position, drawn in different colors. Inside each matchbox are several colored beads, one for each move on the top. When it is the machine’s turn to move, the human operator finds the matchbox showing the current position, draws a bead at random from the matchbox, replaces it, and makes the move thus chosen. The machine learns from its losses: when it loses, the operator removes and discards the last bead drawn. This ensures that the machine will never lose in this way again.

In our implementation, we use a data type for the board positions, and use this as the key (index) in an associative array to get a list of possible moves (the data). Just as in the mechanical version, the program picks one move at random. If the program loses, it deletes the last move chosen from that list.

Our implementation has a few extra goodies not found in the mechanical version. First, it generates the possible positions and lists of moves automatically as they are needed, rather than requiring them to be figured out in advance. Second, because of this, we let the machine play either White or Black or both (it can play against itself). Third, its organization in terms of objects allows the same algorithms to be used for other board games such as Tic Tac Toe, by overriding some methods to customize it for the game of interest.

To play Hexapawn, execute the statements in Listing 4 with Do It. A window comes up which prompts for White’s move. The squares of the board are numbered across, then down, as

 (Black)
 1 2 3
 4 5 6
 7 8 9
 (White).

Enter the move as a “from” digit, a space, and a “to” digit. E.g. for White to move from the lower-left corner forward one, enter “7 4” and click on the Move button. To give up, enter “resign”. (You can also force a win by entering “win”, although this is cheating except when used by authorized testers.)

Implementation Notes

These are miscellaneous notes to help you understand the implementation.

1. The matchboxes are implemented as the ComputerPlayer instance variable matchboxes, and are updated and read in ComputerPlayer’s instance methods youLose and yourMove. Note that these methods do not assume any particular format for the moves, and Hexapawn and Tic Tac Toe use different formats. This is one of the benefits of Smalltalk’s lack of strong typing.

2. The top class for this program is GameMonitor, and all other classes are subclasses of it. GameMonitor includes all the methods for updating the window, and was placed at the top so any object could write to the log just by executing self loggit: ‘message’. (This is also a sneaky way of introducing global variables: the class variables of GameMonitor are accessible in all of its subclasses.) The two immediate subclasses of GameMonitor are GameBoard and Player. GameBoard is responsible for knowing all the rules of the game. Player is responsible for providing moves and for deciding whether the player has lost, won, or should continue playing. Player has two immediate subclasses, ComputerPlayer and HumanPlayer. ComputerPlayer contains the methods for generating new moves by examining the matchboxes, while HumanPlayer has methods for obtaining the next move from the human who is playing.

3. The main loop of the game is in moveOver. It determines the next active Player and sends it a yourMove message. The Player takes whatever steps are necessary to make a correct move (the move itself is performed by sending oneself a move: message), and then sends moveOver to itself. The cycle repeats until one Player declares himself the winner, or all Players have resigned (so the Cat wins).

4. A HumanPlayer obtains a move by sending requestMove to itself (which goes up to the GameMonitor). The GameMonitor displays the prompt in the window. When the human clicks on the Move button, this is a change in its window so readMove: is issued, which then looks up who it is who wanted a move and sends him a haveProposedMove: message. The HumanPlayer is responsible for editing and validating the move if necessary. It is also responsible for retrying if the move was illegal.

5. To add a new game, add new subclasses of GameBoard, ComputerPlayer, and HumanPlayer. To GameBoard add methods for new, allLegalMoves, move:, and reset. To ComputerPlayer add methods for yourMove (if the default is not adequate). To HumanPlayer add methods for haveProposedMove: and yourMove. Note that most of these are implemented in the parent class as self implementedBySubclass, which will generate an error if they are issued in the game but were not overridden.

6. This implementation (and Gardner’s) does not take advantage of symmetries in the game; e.g. in Hexapawn there is a horizontal symmetry, so that when a player has learned moves on the left-hand side of the boards he might apply these on the right-hand side without having played there before. This could be implemented by additional checks in the Dictionary lookup: if the current position is not found, reflect it across the vertical axis and try again.

Smalltalk Gotchas

This is a list of things that may trip you up in working with Smalltalk and Smalltalk/V Mac.

1. In most languages variables “have values” but in Smalltalk variables “refer to objects”. In other words all variables are pointers. This means that the traditional method of saving the value of X by setting saveX := X doesn’t work -- this just makes saveX refer to the same object as X, and an operation on X automatically has the same effect on saveX. (Actually this is usually not a problem for “simple” objects, since operations on them usually do not alter the object but instead return a new object which shows the alteration. But collections are usually updated “in-place”, i.e. the same object is returned after alterations, so it is a problem for them.) To get around this, you have to use the copy or deepCopy methods to make a new copy of the object. For example, this program uses one object to be the board position, and it is saved (e.g. for creating a new Dictionary entry) by applying deepCopy to it. Another method is used for the trialMove in allLegalMoves; since a legal trialMove will be added to the OrderedCollection, we do not want it changing after we have added it, and so we make each one a new object.

2. Equality (=) does not always have its obvious meaning in Smalltalk. You are allowed to define equality when you define a new class. The default definition is inherited from the parent class. In the original Object class, equality is defined to be the same as identity, i.e. x = y if and only if x and y refer to the same object, and two objects which have the same values for their instance variables are not equal. In the derived class of Array, equality is defined as equality of corresponding elements in the array, as one would expect. Dictionary lookups search for an element that is equal to the given key, so if you use a class of your own definition as a Dictionary key, be sure to define equality for the class. Since the Dictionary uses hashing to make its initial search, if you define equality you must also define hash in such a way that equal objects always have the same hash value. See the discussion on pp. 96-7 of Smalltalk-80: The Language and Its Implementation, Goldberg and Robson, Addison-Wesley, 1983.

3. The discussion of windows in the Smalltalk/V Mac manual (pp. 218-230) is very confusing, although the windows themselves operate fairly simply.

Here are some additional explanations of the manual’s explanation:

• The application model is an object to which messages are sent when something interesting (usually a change) happens in a pane. In this program the methods are all defined at the top level (in GameMonitor), and the model was somewhat arbitrarily chosen to be the board object.

• The message sent when a change occurs is the one specified in an earlier change: message. E.g. if change: #blorg was executed earlier for the subpane, then when a change occurs the message blorg is sent to the application model for that subpane. The Dispatcher for a window tends to run asynchronously from everything else, and a message is how you get notified when it detects a change.

• Usually the subpanes of a given window show related information, and if one subpane changes the others may need to change too. The method specified in change: is responsible for figuring out what kind of changes are needed; it uses the method specified earlier in the name: message to carry these out.

• The method specified in a name: message issued for a given subpane is used for three different purposes. First, it is issued by most types of Panes when the window is opened to initialize the contents of the Pane. Second, it identifies a type of change (it is really the name of a change, not the name of the subpane -- different subpanes can have the same name, which just means that they will be changed under the same conditions). Third, it is usually the name of the method that will be invoked (by sending a message to the application model) to carry out the change. When the method specified in change: decides what changes are needed in other subpanes, it issues changed: messages with the desired name as argument. So if blorg decides that all subpanes with name meToo should be updated, it sends a changed: #meToo to the model. The model issues update: #meToo to its dependents, i.e. all the subpanes whose model it is. Those subpanes for which name: specified meToo send update (not update:) messages to themselves. The update method should refresh the subpane’s display with current data. The changed:with: method allows some more flexibility: changed: #meToo with: #somethingElse again selects those subpanes for which name: specified meToo, but instead of performing update they perform somethingElse.

Simple, isn’t it? This game-playing program does not require any coordination between subpanes, so all the name: messages specify methods which initialize the panes but do no updates.

4. When you define a new class (call it Klass), Show It and the Inspector display instances of it as “a Klass” without telling you the value. To fix this define printOn: for your new class, since Show It and the Inspector call printOn: to display the value. Usually you would display the instance variables, strung together with some punctuation marks. If the classes for the instance variables already have printOn: defined, you can call printOn: for each variable to get the printable values.

For Further Reading

David H. Ahl (ed.), BASIC Computer Games. Workman Press, 1978. Gives a more conventional implementation of Hexapawn, on pp. 83-4. It uses two 2-dimensional arrays, one to list the board positions and a corresponding one to list the moves from that position. Warning: there are several errors in the tables; another good reason to let the computer do the work for us.

Mike™ Scanlin, “Create a Tic Tac Toe Game!”. The Complete MacTutor, v. 2, pp. 73-85. Gives a more conventional implementation of Tic Tac Toe, written in assembler. This program plays by strategy, rather than from a list of moves, and does no learning.

Caxton C. Foster, Content-Addressable Parallel Processors. Van Nostrand Reinhold, 1976. Really has nothing to do with this article, but an interesting book anyway. Contains many clever algorithms for associative memories, but their interest depends on being able to do all the steps in parallel, and would not be interesting implemented on a serial computer.

Martin Gardner, “Mathematical Games”. Scientific American, March 1962. Reprinted in his The Unexpected Hanging and Other Mathematical Diversions, Chapter 8. Simon and Schuster, 1972. Defines the game of Hexapawn and shows its implementation in matchboxes.

Donald E. Knuth, Sorting and Searching (The Art of Computer Programming, v. 3). Addison-Wesley, 1973. The usual method of searching associative arrays, and the method used by Smalltalk, is hashing. Pages 506-559 of this book discusses hashing.

This program is written in Smalltalk/V Mac, version R1.10. Listings 1-3 are in File In format.

Listing 1.  Common classes for all games.
(File:  GameMonitor.st)
"*************************************************"
"* special classes to override built-in behavior *"
"*                                               *"
"* MyButtonPane bypasses the checks for 'text    *"
"* modified' when a button is pressed, and       *"
"* MyGraphPane eliminates scroll bars on the     *"
"* pane.                                         *"
"*************************************************"

ButtonPane subclass: #MyButtonPane
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!MyButtonPane class methods ! !

!MyButtonPane methods !

selectAtCursor
    "Press the button at the current cursor position."
    | |
    1 to: boxes size do: [ :i |
        ((boxes at: i) containsPoint: Cursor offset)
            ifTrue: [ ^ self buttonPressed: i ]
    ].! !

GraphPane subclass: #MyGraphPane
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!MyGraphPane class methods ! !

!MyGraphPane methods !

addMenus: menuBar
    "dummy for addSubPane"
    "needed to eliminate scroll bars on GraphPane"
    | |! !

"********************************"
"* begin Game Monitor           *"
"********************************"
Object subclass: #GameMonitor
  instanceVariableNames: ''
  classVariableNames:
    'CatWins ActivePlayers PromptPane MoveRequestor 
     AllPlayers LogPane GetMovePane TheBoard WhoseMove 
     GameOver '
  poolDictionaries: '' !

!GameMonitor class methods !

initialize: aBoard
        "Create the monitor panes with aBoard as model,
         also initialize any variables whose value 
         persists across games."
    | topPane |
    (topPane := TopPane new) label: 'Monitor'.
    topPane addSubpane:
        (PromptPane := MyGraphPane new model: aBoard;
            name: #dummyUpdate1:;
            framingRatio: (0@0 extent: 2/3 @ (1/6))).
    topPane addSubpane:
        (GetMovePane := TextPane new model: aBoard;
            name: #dummyUpdate;
            framingRatio: (0@(1/6) extent: 2/3 @ (1/6))).
    topPane addSubpane:
        (LogPane := TextPane new model: aBoard;
            name: #dummyUpdate;
            framingRatio: (0@(1/3) extent: 1@(2/3))).
    topPane addSubpane:
        (MyButtonPane new model: aBoard;
            buttons: #(Move);
            change: #readMove:;
            pulse: true;
            framingRatio: (2/3 @ 0 extent: 1/3 @ (1/3))).

    "initialize persistent values"
    CatWins := 0.
    TheBoard := aBoard.! !

!GameMonitor methods !

dummyUpdate
        "private - do nothing to update TextPane"
    | |
    ^'' "have to send back something, or it won't work"!

dummyUpdate1: aRect
        "private - initialize form for GraphPane"
    | aForm |
    aForm := Form
        width: aRect width
        height: aRect height.
        aForm white; offset: aRect origin.
    ^aForm.!

gameOver
        "private - called from moveOver if 
         the game is now over"
    | playAgain |
    self loggit: '---game over'.
    "ask for another game"
    self loggit:
        'Scores: (Cat got ',
            (CatWins printPaddedTo: 4) , ')'.
    AllPlayers do: [:aPlayer | aPlayer printScore].

    "To have the computer play itself continuously, the
     following statement should be replaced with
        playAgain := 'Yes'."
    playAgain :=Prompter prompt: 'Play again?'
                    default: 'Yes'.
    (playAgain = 'Yes')
        ifTrue: [ TheBoard reset. self restartPlayers ]
        ifFalse: [self loggit: '***play is over'.
                  "this releases the players and board"
                  AllPlayers := nil.
                  TheBoard := nil.].!

loggit: aString
        "write aString to the LogPane, supplying the Cr"
    | |
    LogPane appendString: aString;
            appendChar: (CharacterConstants at: 'Cr');
            displayChanges.!

moveOver
        "This is the main loop of the monitor.  If the 
         game is not over yet, it determines the next 
         active player and tells him to make a move.  
         If the game is over, it so states, prints 
         statistics, and asks if you want to play 
         again."

        "A game is over either when one player declares
         himself the winner, or if all players have 
         resigned."
    | |
    TheBoard showBoard.
    GameOver
        ifFalse: [ "move to next player"
                    WhoseMove := WhoseMove \\ 
                                 (AllPlayers size) + 1.
                    [ActivePlayers at: WhoseMove] 
                        whileFalse:
                        [WhoseMove := WhoseMove \\ 
                                 (AllPlayers size) + 1].
                    (AllPlayers at: WhoseMove) yourMove.
                ]
        ifTrue: [ self gameOver ].!

readMove: whichButton
        "private - Send the move read (the entire text)
         to the requestor.  Argument whichButton is not
         used, since there's only one button"
    | holdRequestor theMove |
    holdRequestor := MoveRequestor.
    theMove := GetMovePane contents.
    "kludge to eliminate trailing Cr"
    ((theMove at: (theMove size)) = 
    (CharacterConstants at: 'Cr'))
        ifTrue: [theMove := 
             theMove copyFrom:1 to: (theMove size - 1)].
    "now clear the panes, and the requestor"
    PromptPane form white. 
 PromptPane update; showWindow.
    GetMovePane selectAll; replaceWithText: ''; update.
    MoveRequestor := nil.
    holdRequestor haveProposedMove: theMove.!

requestMove: aPrompt
        "request the human player to make a move 
         by saying aPrompt"
    | aPen |
    MoveRequestor := self.
    (Pen new: (PromptPane form))
        defaultNib: 1;
        place: ((PromptPane form extent) // 2);
        centerText: aPrompt 
            font: (Font applicationFont).
    PromptPane showWindow.
    "the move wil be returned in a haveProposedMove 
     message"!

resign
        "A player resigns from the game, or admits 
         defeat.  If all players resign, the Cat wins"
    | |
    self loggit: (self name) , ' says he resigns ' .
    ActivePlayers at: WhoseMove put: false.
    "game is over if there are no move players"
    (ActivePlayers includes: true)
        ifFalse: [GameOver := true.
                    CatWins := CatWins + 1.].
    self moveOver.!

restartPlayers
        "private - start players at beginning of game"
    | |
    GameOver := false.
    1 to: (AllPlayers size) do: [:i |
            ActivePlayers at: i put: true].
    AllPlayers do: [:aPlayer |
                        aPlayer newGame].
    WhoseMove := 1.
    (AllPlayers at: WhoseMove) yourMove.!

startPlay: allPlayers
        "record the Array of all Players"
        "call the first player"
    | topPane |
    topPane := LogPane topPane.
    topPane dispatcher open.
    AllPlayers := allPlayers.
    ActivePlayers := Array new: (allPlayers size).
    self restartPlayers.
    topPane dispatcher scheduleWindow.!

win
        "declare oneself the winner"
    | |
    self loggit: (self name) , ' says he wins'.
    GameOver := true.
    "notify all players of status"
    AllPlayers do: [:aPlayer |
        (aPlayer = self)
            ifTrue: [aPlayer youWin]
            ifFalse: [aPlayer youLose]].
    self moveOver.! !

"******************************"
"* GameBoard class definition *"
"******************************"
GameMonitor subclass: #GameBoard
  instanceVariableNames:
    'width height positions '
  classVariableNames: ''
  poolDictionaries: '' !

!GameBoard class methods ! !

!GameBoard methods !

allLegalMoves
        "answer an OrderedCollection of
         all valid moves from this position"
    | |
    self implementedBySubclass.!

getPositions
        "answer a copy of the array of the 
         board position"
    | |
    ^ positions deepCopy.!

move: m
        "Record a move by player WhoseMove"
        "Answer:
                #Win,   if the player wins on this move
                #Ok,    if this is a legal move
                #Error, if this is an illegal move 
                        (and do not record the move)"
    | |
    self implementedBySubclass.!

reset
        "reset the board back to the start"
    | |
    self implementedBySubclass.!

setWidth: w height: h
        "private - initialize board dimensions"
    | |
    width := w.
    height := h.!

showBoard
        "display the current board position"
        "subclasses may override this
         to get a different display"
    | oneLine aPlayer |
    1 to: height do:
        [:row | oneLine := ''.
                1 to: width do:
                    [:col |
                        aPlayer := positions at: 
                                width*(row - 1) + col.
                        aPlayer isNil
                            ifTrue:
                                [aPlayer := '.']
                            ifFalse:
                                [aPlayer := 
                     (AllPlayers at: aPlayer) marker].
                        oneLine := oneLine , aPlayer.
                    ].
                    self loggit: oneLine.
        ]! !

"******************************"
"* Player class definition    *"
"******************************"
GameMonitor subclass: #Player
  instanceVariableNames:
    'gamesWon whoAmI marker '
  classVariableNames: ''
  poolDictionaries: '' !

!Player class methods !

new: aName marker: aMarker
        "create a new instance for player aName;
         aMarker will mark his pieces on the board"
    | aPlayer |
    aPlayer := super new.
    aPlayer name: aName marker: aMarker.
    aPlayer clear.
    ^ aPlayer! !

!Player methods !

clear
        "private - clear any needed variables"
    | |
    gamesWon := 0.!

haveProposedMove: aMove
        "send the proposed move, yielded by
         requestMove:, to the original requestor"
    | |
    self implementedBySubclass!

marker
        "answer the marker of this player"
    | |
    ^ marker.!

name
        "answer the player's name"
    | |
    ^ whoAmI!

name: aName marker: aMarker
        "private - record name and marker of new player"
    | |
    whoAmI := aName.
    marker := aMarker.!

newGame
        "reinitialize for new game - 
         subclasses may supplement this"
    | |!

printScore
        "private - print the number of games won 
         on the LogPane"
    | |
    self loggit: whoAmI , (gamesWon printPaddedTo: 4).!

youLose
        "Sent to player at end of game, if he lost."
        "May be supplemented in subclass."
    | |!

yourMove
        "tells a Player it is his move"
    | |
    self implementedBySubclass!

youWin
        "Sent to player at end of game, if he won."
        "May be supplemented in subclass."
    | |
    gamesWon := gamesWon + 1.! !

Player subclass: #ComputerPlayer
  instanceVariableNames:
    'matchboxes lastMove lastBoardPosition '
  classVariableNames: ''
  poolDictionaries: '' !

!ComputerPlayer class methods !

new: aName marker: aMarker
        "create a new ComputerPlayer"
    | aPlayer |
    aPlayer := super new: aName marker: aMarker.
    aPlayer createMatchboxes.
    ^aPlayer.! !

!ComputerPlayer methods !

createMatchboxes
        "private - create the Dictionary 
         of matchboxes upon new:"
    |  |
    matchboxes := Dictionary new.!

newGame
        "clear detritus from previous game"
    | |
    lastMove := nil.
    lastBoardPosition := nil.!

"**********************************************"
"* The matchboxes are implemented in youLose  *"
"* and yourMove.                              *"
"**********************************************"
youLose
        "delete the losing move from the matchboxes"
    | tempMoves |
    lastBoardPosition isNil
        ifTrue: 
            [self error: 'ComputerPlayer can''t move']
        ifFalse: 
            [tempMoves := 
                    (matchboxes at: lastBoardPosition)
                                 deepCopy.
             tempMoves remove: lastMove.
                matchboxes at: lastBoardPosition
                           put: tempMoves.
            ]. !

yourMove
        "generate the next move for this player"
    | theMoves copyBoardPosition moveResult |
    copyBoardPosition := TheBoard getPositions.
    (matchboxes includesKey: copyBoardPosition)
        ifFalse: [ "new position - add all 
                    possible moves"
            matchboxes at: copyBoardPosition
                       put: (TheBoard allLegalMoves)
            ].
    theMoves := matchboxes at: copyBoardPosition.
    ((theMoves size)=0)
        ifTrue: [ "we are blocked - resign"
            self resign. ^nil]
        ifFalse: [
            "pick a move at random, and remember the 
             move in case it is a loser"
            lastMove := theMoves at:
                (1 + (SmallInteger random: 
                        (theMoves size))).
            lastBoardPosition := copyBoardPosition.
            moveResult := (TheBoard move: lastMove).
            (moveResult = #Win)
                ifTrue: [self win]
                ifFalse:[ (moveResult = #Ok)
                            ifTrue: [ self moveOver ]
                           ifFalse:
                                ["no good - 
                                    internal error"
                                 self error: 
                                     'ComputerPlayer ' ,
                                     'attempted ',
                                     'illegal move' ].
                        ]
                    ]! !

Player subclass: #HumanPlayer
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!HumanPlayer class methods ! !

!HumanPlayer methods !

retryMove
        "ask human to try again - his move was no good"
    | |
    self loggit: 'Try again!!'; yourMove.!

yourMove
        "ask the human for his move;
         it will be returned in a 
         haveProposedMove message"
    | |
    self requestMove: whoAmI , '''s move?'! !
Listing 2.  Additional classes for Hexapawn.
(File:  Hexapawn.st)
GameBoard subclass: #HexapawnGameBoard
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!HexapawnGameBoard class methods !

new
        "create a new instance"
    | aBoard |
    aBoard := super new.
    aBoard setWidth:3 height:3.
    aBoard reset.
    ^aBoard.!

validCaptureMovement: m player: p
        "private - answer whether m is a valid capture 
         movement according to the rules of Hexapawn, 
         i.e. it is a diagonal move."
    | distance rem |
    distance := (m at: 2) - (m at: 1).
    (p = 1) ifFalse: [ distance := distance - 6 ].
    rem := (m at: 1) \\ 3.
    (rem = 0) ifTrue:[^(distance = -4)].
    (rem = 1) ifTrue:[^(distance = -2)].
    (rem = 2) ifTrue:[^(distance = -4) | 
                       (distance = -2)].!

validForwardMovement: m player: p
        "private - answer whether m is a valid forward 
         movement according to the rules of Hexapawn, 
         i.e. it is forward one"
    | distance |
    distance := (m at: 2) - (m at: 1).
    (p = 1) ifFalse: [ distance := distance negated ].
    ^ (distance = -3).! !

!HexapawnGameBoard methods !

allLegalMoves
        "answer an OrderedCollection
         of all valid moves from this position"
    | trialMove answer|
    answer := OrderedCollection new.
    1 to: 9 do: [:from |
        ((positions at: from) = WhoseMove) ifTrue: [
            1 to: 9 do: [:to |
                trialMove := Array new: 2.
                trialMove at:1 put: from; at:2 put: to.
                (self legalMove: trialMove)
                    ifTrue: [answer add: trialMove].
                ]
            ]
        ].
    ^ answer.!

legalMove:m
        "Answer whether m is a legal movement for this 
         position."
    | fromSq toSq freeMove captureMove |
        fromSq := m at: 1.
        toSq   := m at: 2.
        freeMove :=
            ((positions at: fromSq) = WhoseMove) &
            ((positions at: toSq)   = nil ) &
            (HexapawnGameBoard 
                validForwardMovement: m 
                player: WhoseMove).
        captureMove :=
            ((positions at: fromSq) = WhoseMove) &
            ((positions at: toSq) ~= WhoseMove) &
            ((positions at: toSq) ~= nil) &
            (HexapawnGameBoard validCaptureMovement: m
                                    player: WhoseMove).
        ^ (freeMove | captureMove).!

move: m
        "Record a move from m.1 to m.2 by player
         WhoseMove."
    | |
    self loggit: ((AllPlayers at: WhoseMove) name) ,
                 ' moves ' ,
                 ((m at: 1) printPaddedTo: 1), ' ' ,
                 ((m at: 2) printPaddedTo: 1).
    (self legalMove: m) ifTrue:
        [ "make move"
        positions at: (m at: 1) put: nil.
        positions at: (m at: 2) put: WhoseMove.
            ((m at: 2) - 1 // 3 = 1)
                ifTrue: [ "moved to middle row"
                        ^ #Ok]
                ifFalse: [ "moved to last row"
                        ^ #Win].
        ].
    ^ #Error. "don't make the move"!

reset
        "set the board to its initial position"
    | |
    positions isNil
        ifTrue: [positions := Array new: 9].
    positions at: 1 put: 2;
                at: 2 put: 2;
                at: 3 put: 2;
                at: 4 put: nil;
                at: 5 put: nil;
                at: 6 put: nil;
                at: 7 put: 1;
                at: 8 put: 1;
                at: 9 put: 1.! !

ComputerPlayer subclass: #HexapawnComputerPlayer
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!HexapawnComputerPlayer class methods ! !

!HexapawnComputerPlayer methods !

yourMove
        "check whether all opponents are gone 
         (if so, we win);
         otherwise request another move from the
         general move-finder"
    | |
    ((ActivePlayers occurrencesOf: true) = 1)
        ifTrue: [self win]
        ifFalse: [super yourMove].! !

HumanPlayer subclass: #HexapawnHumanPlayer
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!HexapawnHumanPlayer class methods ! !

!HexapawnHumanPlayer methods !

haveProposedMove: aMove
        "Check for valid format.  The format is:
         the from-square number, a blank, and the
         to-square number.  E.g. 
         7 4
         moves from 7 to 4."
    | moveResult arrayMove |
    (aMove = 'win') ifTrue: [self win. ^nil].
    (aMove = 'resign' ) ifTrue: [self resign. ^nil].
    (aMove size) < 3
        ifTrue: [self retryMove]
        ifFalse: [
    ((aMove at: 1) isDigit) & ((aMove at: 3) isDigit)
        ifTrue: [
            arrayMove := Array new: 2.
            arrayMove 
                at: 1 put: ((aMove at: 1) digitValue);
                at: 2 put: ((aMove at: 3) digitValue).
            moveResult := (TheBoard move: arrayMove).
            (moveResult = #Win)
                ifTrue: [self win]
                ifFalse:[ (moveResult = #Ok)
                            ifTrue: [ self moveOver ]
                            ifFalse:
                                [ self retryMove ].
                        ]
                ]
        ifFalse: [ self retryMove ].
        ]!

yourMove
        "check whether all opponents are gone 
         (if so, we win);
         otherwise request another move from the human"
    | |
    ((ActivePlayers occurrencesOf: true) = 1)
        ifTrue: [self win]
        ifFalse: [super yourMove].! !
Listing 3.  Additional classes for Tic Tac Toe.
(File:  TicTacToe.st)
GameBoard subclass: #TicTacToeGameBoard
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!TicTacToeGameBoard class methods !

new
        "create a new instance"
    | aBoard |
    aBoard := super new.
    aBoard setWidth:3 height:3.
    aBoard reset.
    ^aBoard.! !

!TicTacToeGameBoard methods !

allLegalMoves
        "Answer an OrderedCollection of all legal 
         moves.  For TicTacToe, any move that is not 
         an occupied space is legal"
    | answer |
    answer := OrderedCollection new.
    1 to: (width*height) do:
        [:i | (positions at: i) isNil
                   ifTrue: [answer add: i].
        ].
    ^answer.!

move: m
        "Record a move by player WhoseMove.
         In TicTacToe, any move into a vacant square 
         is legal, and three pieces in a row wins."
    | |
    self loggit: ((AllPlayers at: WhoseMove) name) ,
                 ' moves ' , (m printPaddedTo: 1).
    (positions at: m) isNil
        ifTrue: [positions at: m put: WhoseMove.
                 (self threeAcross: m) |
                 (self threeDown: m) |
                 (self threeDiagonally: m)
                    ifTrue: [^#Win]
                    ifFalse: [^#Ok].
                ]
        ifFalse: [^#Error].!

reset
        "reset the board back to the start"
    | |
    positions isNil
        ifTrue: 
            [positions := Array new: (width * height)].
    1 to: (width * height) do: 
        [:i | positions at: i put: nil].!

threeAcross: aMove
        "answer whether WhoseMove has three marks 
         across, one of which is aMove"
    | rowStart answer |
    rowStart := ((aMove - 1) // 3) * 3 + 1.
    answer := true.
    rowStart to: (rowStart + 2) do: [ :i |
        answer := answer & 
                    ((positions at: i) = WhoseMove)].
^ answer.!

threeDiagonally: aMove
        "answer whether WhoseMove has three marks
         diagonally (aMove is not used)"
    | answer1 answer2 |
    answer1 := true.
    answer2 := true.
    1 to: 9 by: 4 do: [ :i |
        answer1 := answer1 & 
                    ((positions at: i) = WhoseMove)].
    3 to: 7 by: 2 do: [ :i |
        answer2 := answer2 & 
                    ((positions at: i) = WhoseMove)].
^ (answer1 | answer2).!

threeDown: aMove
        "answer whether WhoseMove has three marks down,
         one of which is aMove"
    | colStart answer |
    colStart := (aMove - 1) \\ 3 + 1.
    answer := true.
    colStart to: (colStart + 6) by: 3 do: [ :i |
        answer := answer & 
                    ((positions at: i) = WhoseMove)].
^ answer.! !

ComputerPlayer subclass: #TicTacToeComputerPlayer
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!TicTacToeComputerPlayer class methods ! !

!TicTacToeComputerPlayer methods ! !

HumanPlayer subclass: #TicTacToeHumanPlayer
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: '' !

!TicTacToeHumanPlayer class methods ! !

!TicTacToeHumanPlayer methods !

haveProposedMove: aMove
        "Check for valid format.  The format is:
         a single digit giving the space to move
         to."
    | moveResult |
    (aMove = 'win') ifTrue: [self win. ^nil].
    (aMove = 'resign' ) ifTrue: [self resign. ^nil].
    (aMove size) < 1
        ifTrue: [self retryMove]
        ifFalse: [
    (aMove at: 1) isDigit
        ifTrue: [
            moveResult := 
                (TheBoard move: aMove asInteger).
            (moveResult = #Win)
                ifTrue: [self win]
                ifFalse:[ (moveResult = #Ok)
                            ifTrue: [ self moveOver ]
                            ifFalse:
                                [self retryMove].
                        ]
            ]
        ifFalse: [self retryMove].
        ]! !
Listing 4.  Code to play games.
(File:  play games)
"Select the following statements and execute 
 with Do It to play Hexapawn against the 
 computer (you play White)."

|p1 p2 board allPlayers|
board := HexapawnGameBoard new.
GameMonitor initialize: board.
p1 := HexapawnHumanPlayer new: 'White' marker: 'W'.
p2 := HexapawnComputerPlayer new: 'Black' marker: 'B'.
allPlayers := Array new: 2.
allPlayers at: 1 put: p1; at: 2 put: p2.
board startPlay: allPlayers.

"Select the following statements and execute
 with Do It to play Tic Tac Toe against the
 computer (you play X, which moves first)."

|p1 p2 board allPlayers|
board := TicTacToeGameBoard new.
GameMonitor initialize: board.
p1 := TicTacToeHumanPlayer new: 'X' marker: 'X'.
p2 := TicTacToeComputerPlayer new: 'O' marker:'O'.
allPlayers := Array new: 2.
allPlayers at: 1 put: p1; at: 2 put: p2.
board startPlay: allPlayers.

 
AAPL
$519.01
Apple Inc.
+1.05
MSFT
$40.40
Microsoft Corpora
+0.65
GOOG
$556.54
Google Inc.
+20.10

MacTech Search:
Community Search:

Software Updates via MacUpdate

PDFpenPro 6.2 - Advanced PDF toolkit for...
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Create... Read more
PDFpen 6.2 - Edit and annotate PDFs with...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
Monolingual 1.5.9 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
MYStuff Pro 2.0.16 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
TurboTax 2013.r17.002 - Manage your 2013...
TurboTax guides you through your tax return step by step, does all the calculations, and checks your return for errors and overlooked deductions. It lets you file your return electronically to get... Read more
TrailRunner 3.8.769 - Route planning for...
Note: While the software is classified as freeware, it is actually donationware. Please consider making a donation to help support development. TrailRunner is the perfect companion for runners,... Read more

Latest Forum Discussions

See All

Unpossible (Games)
Unpossible 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: **Important** Requires at least iPad 2, iPhone 4S, iPod Touch (5th gen), or newer. | Read more »
Hitman GO (Games)
Hitman GO 1.2 Device: iOS Universal Category: Games Price: $4.99, Version: 1.2 (iTunes) Description: Get your daily fix of Agent 47 with this elegant, strategy-based Hitman game! | Read more »
The Seventh Sign: Hodappy Bird Released...
The Seventh Sign: Hodappy Bird Released on the App Store Posted by Jeff Scott on April 16th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Rogue Heroes (Games)
Rogue Heroes 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Rogue Heroes is awesome fast-paced 2D action-platforming roguelike game with RPG elements. - explore the depth of procedurally... | Read more »
Fourcast Review
Fourcast Review By Jennifer Allen on April 16th, 2014 Our Rating: :: VIDEO POTENTIALiPhone App - Designed for the iPhone, compatible with the iPad Fourcast is a great idea for combining video clips, but it does lack a number of... | Read more »
Hearthstone: Heroes of Warcraft is Avail...
Hearthstone: Heroes of Warcraft is Available on the U.S. App Store Right Now – Gogogogo! Posted by Rob Rich on April 16th, 2014 [ permalink ] | Read more »
Grammar Pop HD Review
Grammar Pop HD Review By Jennifer Allen on April 16th, 2014 Our Rating: :: FUN LEARNINGiPad Only App - Designed for the iPad Learning the different parts of speech isn’t always fun, but Grammar Pop HD makes it much more... | Read more »
Groundskeeper2 Review
Groundskeeper2 Review By Nadia Oxford on April 16th, 2014 Our Rating: :: SLICE THOSE ALIEN SLIMEUniversal App - Designed for iPhone and iPad Putting aside some minor control issues, Groundskeeper2 is a fun and furious action/... | Read more »
Pinnacle Studio for iPhone (Photography...
Pinnacle Studio for iPhone 5.0 Device: iOS iPhone Category: Photography Price: $9.99, Version: 5.0 (iTunes) Description: | Read more »
Season 3 of Zombies, Run! Starts Right N...
Season 3 of Zombies, Run! | Read more »

Price Scanner via MacPrices.net

Microsoft Blinks – Drops Microsoft Office 365...
Microsoft has dropped the annual subscription fee for Microsoft Office 365 Personal – which is needed in order to create and edit documents in Microsoft Office for iPad. However, Apple’s iOS and OS X... Read more
New AVG Vault Apps for iOS and Android Help K...
AVG Technologies N.V. an online security company for 177 million active users, has announced the launch of its latest mobile application, AVG Vault. The free app introduces an innovative user... Read more
Free Local Carrot iPhone App Helps Find Fresh...
I love fresh vegetables. I’m not a vegan, although I was for several years in the 1980s, but fresh vegetables and other whole foods are still my dietary mainstays as a matter of taste rather than... Read more
Apple refurbished iPad Airs available startin...
Apple is now offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. The following Airs are available today: -... Read more
21-inch 2.7GHz iMac on sale for $1179, save $...
B&H Photo has the 21″ 2.7GHz iMac on sale for $1179 including free shipping plus NY sales tax only. Their price is $120 off MSRP. Add an iMac to your shopping cart, and B&H will offer an... Read more
Download our app, iTracx, for iOS and Android
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
Education discounts shave up to $300 off the...
Purchase a new Mac at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free, and all... Read more
Save $50 on Mac mini Server
B&H Photo has the 2012 Mac mini Server on sale for $949 including free shipping plus NY sales tax only. Their price is $50 off MSRP. Read more
PhatWare’s “Ultimate Writing App For iOS” Ren...
PhatWare Corp. has announced it has renamed its new WritePro word processing app for iPhone and iPad: WritePad Pro. The decision to change the app’s name to leverages the strong brand awareness and... Read more
Full Resolution Photo Editor Tint Mint 1.0 Re...
California based independent developer, Jeffrey Sun, creator of the iOS app Modern Editor, has released Tint Mint, a new photography app for editing enthusiasts. The app costs a dollar, and it packs... Read more

Jobs Board

*Apple* Retail - Manager - Holyoke - Apple I...
Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you’re a master of them all. In the store’s fast-paced, Read more
*Apple* Retail - Manager - Apple (United Sta...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Retail - Market Leader - Cincinnati...
…challenges of developing individuals, building teams, and affecting growth across Apple Stores. You demonstrate successful leadership ability - focusing on excellence Read more
*Apple* Retail - Manager - SoHo - Apple (Uni...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.