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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

iExplorer 4.1.10 - View and transfer fil...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
iExplorer 4.1.10 - View and transfer fil...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
Adobe InCopy CC 2018 13.0.1.207 - Create...
InCopy CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous InCopy customer). Adobe InCopy CC 2018, ideal for large team projects... Read more
Microsoft Office 2016 15.40 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
Adobe InDesign CC 2018 13.0.1.207 - Prof...
InDesign CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous InDesign customer). Adobe InDesign CC 2018 is part of Creative Cloud.... Read more
Apple iOS 11.1.2 - The latest version of...
iOS 11 sets a new standard for what is already the world’s most advanced mobile operating system. It makes iPhone better than before. It makes iPad more capable than ever. And now it opens up both to... Read more
Slack 2.9.0 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 2.9.0: Slack now officially, and fully, supports Japanese.... Read more
iExplorer 4.1.9 - View and transfer file...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
PCalc 4.5.3 - Full-featured scientific c...
PCalc is a full-featured, scriptable scientific calculator with support for hexadecimal, octal, and binary calculations, as well as an RPN mode, programmable functions, and an extensive set of unit... Read more
iExplorer 4.1.9 - View and transfer file...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more

Latest Forum Discussions

See All

Mighty Battles guide - how to build a so...
Mighty Battles, the latest title from Hothead Games, is set to take the App Store by storm. The game puts a welcome twist on lane battlers, adding FPS elements to spice things up a bit. You'll collect cards to put your own military unit to gether,... | Read more »
Rules of Survival guide - how to be the...
The PUBG craze makes its way to mobile, with more and more battle royale games debuting on iOS and Android. Rules of Survival joins the ranks of mobile PUBG-likes, offering a classic battle royale experiences that doesn't vary too much from its... | Read more »
The best new games we played this week -...
The weekend is upon us friends, and it's time to take a look back and reflect on all of the wonderful games we've played over the past few days. This week was jam packed with new releases. There were some big, long awaited launches, some fun... | Read more »
Lineage II: Revolution guide - tips and...
At long last, Lineage II: Revolution has now come to western shores, bring Netmarble's sweeping MMORPG to mobile devices. It's an addictive, epic experience, but some of the systems in the game can be a bit overwhelming. Here are a few tips to help... | Read more »
A Boy and His Blob (Games)
A Boy and His Blob 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »
Fight terrible monsters and collect epic...
Released on Western markets early last month, Dragon Project, created by Japanese developer COLOPL, brings epic monster hunting action to mobile for the very first time. Collect a huge array of weapons and armor, and join up with friends to fight... | Read more »
I Am The Hero (Games)
I Am The Hero 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: I Am The Hero is a pixel art, beat 'em up, fighting game that tells the story of a "Hero" with a glorious but mysterious past.... | Read more »
Kauldron (Music)
Kauldron 1.0 Device: iOS Universal Category: Music Price: $3.99, Version: 1.0 (iTunes) Description: Kauldron is our warmest sounding, punchiest synth yet! A completely new modeling technology, combined with carefully designed... | Read more »
Lineage II: Revolution is mobile’s bigge...
NCSoft’s hit fantasy MMORPG series has just made the leap to mobile with the help of Netmarble in Lineage II: Revolution. With over 1.5 million players having already pre-registered ahead of the game’s launch, Revolution hit the app stores... | Read more »
Swing skilfully in new physics-based pla...
Sometimes it’s the most difficult of obstacles that can be the most rewarding. One game hoping to prove this is OCMO, the new tough but fair platformer from developers Team Ocmo. Primed to set every speedrunner’s pulse racing, as an otherworldly... | Read more »

Price Scanner via MacPrices.net

Black Friday pricing on Macs and iPads now av...
B&H Photo has lowered prices on many Macs, iPads, and iPad Pros as part of their Black Friday week sale. Save up to $200 on MacBooks and iMacs and up to $150 on iPads. B&H charges sales tax... Read more
Best Apple iPad deals this weekend, up to $80...
Apple resellers are offering 9.7″ iPads and 10.5″ iPad Pros for up to $80 off MSRP this weekend as part of their early Holiday and Black Friday sales: Adorama is offering new 2017 9.7″ 32GB WiFi... Read more
Early Black Friday sale: Apple iMacs for up t...
B&H Photo has 27-inch iMacs in stock and on sale for up $130-$150 off MSRP including free shipping. B&H charges sales tax in NY & NJ only: – 27″ 3.8GHz iMac (MNED2LL/A): $2149 $150 off... Read more
Apple restocks refurbished Mac minis starting...
Apple has restocked Certified Refurbished Mac minis starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: – 1.4GHz Mac mini: $419 $80 off MSRP – 2.6GHz Mac... Read more
Save on 12″ MacBooks, Apple refurbished model...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more
Early Holiday sale: 12″ iPad Pros for up to $...
B&H Photo has 12″ iPad Pros on sale today for up to $130 off MSRP. Shipping is free, and B&H collects no sales tax outside NY & NJ: – 12″ 64GB WiFi iPad Pro: $749, save $50 – 12″ 256GB... Read more
Holiday sale prices on Apple 13″ MacBook Pros...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for $100-$150 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook Pro... Read more
Sale: 13″ MacBook Airs starting at $899, $100...
B&H Photo has 2017 13″ MacBook Airs on sale today for $100 off MSRP including free shipping. B&H charges NY & NJ sales tax only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): $899, $100 off... Read more
Week’s Best Deal on 13″ MacBook Pros: Apple r...
Apple has a full line of Apple Certified Refurbished 2017 13″ MacBook Pros available for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
Deal: 15″ 2.6GHz MacBook Pro for $1799 w/free...
B&H Photo has clearance 2016 15″ 2.6GHz Touch Bar MacBook Pros in stock today and available for $600 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: – 15″ 2.... Read more

Jobs Board

Product Manager - *Apple* Pay on the *Appl...
Job Summary Apple is looking for a talented product manager to drive the expansion of Apple Pay on the Apple Online Store. This position includes a unique Read more
*Apple* Pro/Consumer Apps Support Engineer -...
…exemplify AppleCare's expert technical support paired with exceptional customer service for Apple 's software apps. This person is a problem solver, who understands Read more
Partner Marketing Manager, *Apple* Pay - Ap...
Job Summary The Apple Pay partner marketing team is looking for a Marketing Manager to develop and drive US programs. The right candidate will be passionate about Read more
*Apple* Solution Consultant - Apple (United...
# Apple Solution Consultant - Rochester, MN Job Number: 113037950 Rochester, MN, Minnesota, United States Posted: 19-Sep-2017 Weekly Hours: 40.00 **Job Summary** Are Read more
Sr. Experience Producer, Today at *Apple* -...
# Sr. Experience Producer, Today at Apple Job Number: 56495251 Santa Clara Valley, California, United States Posted: 23-Jun-2017 Weekly Hours: 40.00 **Job Summary** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.