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
$101.06
Apple Inc.
+0.10
MSFT
$47.06
Microsoft Corpora
-0.46
GOOG
$587.37
Google Inc.
-8.71

MacTech Search:
Community Search:

Software Updates via MacUpdate

Monosnap 2.2.2 - Versatile screenshot ut...
Monosnap allows you to save screenshots easily, conveniently, and quickly, sharing them with friends and colleagues at once. It's the ideal choice for anyone who is looking for a smart and fast... Read more
Tunnelblick 3.4beta36 - GUI for OpenVPN...
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
SoftRAID 5.0.4 - High-quality RAID manag...
SoftRAID allows you to create and manage disk arrays to increase performance and reliability. SoftRAID's intuitive interface and powerful feature set makes this utility a must have for any Mac OS X... Read more
Audio Hijack Pro 2.11.3 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Airfoil 4.8.9 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
WhatRoute 1.13.0 - Geographically trace...
WhatRoute is designed to find the names of all the routers an IP packet passes through on its way from your Mac to a destination host. It also measures the round-trip time from your Mac to the... Read more
Chromium 37.0.2062.122 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. FreeSMUG-Free OpenSource Mac User Group build is... Read more
Attachment Tamer 3.1.14b9 - Take control...
Attachment Tamer gives you control over attachment handling in Apple Mail. It fixes the most annoying Apple Mail flaws, ensures compatibility with other email software, and allows you to set up how... Read more
Duplicate Annihilator 5.0 - Find and del...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator detects... Read more
jAlbum Pro 12.2 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more

Latest Forum Discussions

See All

This Week at 148Apps: September 15-19, 2...
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »
Kitty Powers’ Matchmaker – Tips, Tricks,...
Hey There, Kittens: | Read more »
Goblin Sword Review
Goblin Sword Review By Andrew Fisher on September 22nd, 2014 Our Rating: :: RETRO GOODNESSUniversal App - Designed for iPhone and iPad Fun visuals, good music, engaging level design, and lots of content make Goblin Sword an... | Read more »
Major New Update for CSR Racing Adds Fer...
Major New Update for CSR Racing Adds Ferrari and Multiplaye​r Posted by Jessica Fisher on September 22nd, 2014 [ permalink ] | Read more »
Veditor Review
Veditor Review By Jennifer Allen on September 22nd, 2014 Our Rating: :: PIMP YOUR VIDEOUniversal App - Designed for iPhone and iPad Want to add stickers and music to your videos? Veditor can do that easily.   | Read more »
1849′s Nevada Silver DLC is Still Search...
A few months ago, I took a look at 1849 from SomaSim. This Gold Rush-themed city builder for iPad had a fair bit going for it, but lacked in a few crucial areas to make it a true stand-out on the App Store. SomaSim has since added in a sandbox mode... | Read more »
Fruit Ninja Will be Reborn With a Massiv...
Fruit Ninja Will be Reborn With a Massive Update and Origins Animation Series Posted by Jessica Fisher on September 22nd, 2014 [ permalink ] Halfbrick Studios is rebuilding | Read more »
Daniel Tiger’s Grr-ific Feelings Review
Daniel Tiger’s Grr-ific Feelings Review By Amy Solomon on September 22nd, 2014 Our Rating: iPad Only App - Designed for the iPad Daniel Tiger’s Grr-ific Feelings includes activities that allow young children explore different... | Read more »
CloudMagic Updated for iOS 8 – Adds Inte...
CloudMagic Updated for iOS 8 – Adds Interactive Notifications, Share Extension, and More Posted by Jessica Fisher on September 22nd, 2014 [ | Read more »
Starbase Annex (Games)
Starbase Annex 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: "it’s really very clever... a little bit of Hearthstone and a dash of Eclipse" - PocketTactics.com From the creator of Starbase... | Read more »

Price Scanner via MacPrices.net

Apple restocks some refurbished 2014 MacBook...
The Apple Store has restocked some Apple Certified Refurbished 2014 MacBook Airs, with prices starting at $769. An Apple one-year warranty is included with each MacBook, and shipping is free. These... Read more
13-inch 128GB MacBook Air on sale for $949, s...
B&H Photo has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $949.99 including free shipping plus NY tax only. Their price is $50 off MSRP. B&H will also include free copies of... Read more
Apple offering free $25 iTunes Gift Card with...
The Apple Store is offering a free $25 iTunes Gift Card with the purchase of a $99 Apple TV for a limited time. Shipping is free. Read more
Apple refurbished iPod touch available for up...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Most colors are... Read more
iFixIt Tears Down iPhone 6; Awards Respectabl...
iFixit notes that even the smaller 4.7″ iPhone 6 is a giant among iPhones; so big that Apple couldn’t fit it into the familiar iPhone form factor. In a welcome reversal of a recent trend to more or... Read more
Phone 6 Guide – Tips Book For Both iPhone 6...
iOS Guides has announced its latest eBook: iPhone 6 Guide. Brought to you by the expert team at iOS Guides, and written by best-selling technology author Tom Rudderham, iPhone 6 Guide is packed with... Read more
How to Upgrade iPhone iPad to iOS 8 without D...
PhoneClean, a iPhone cleaner utility offered by iMobie Inc., reveals a solution for upgrading iPhone and iPad to iOS 8 without deleting photos, apps, the new U2 album or anything. Thanks to more than... Read more
Inpaint 6 – Photo Retouching Tool Gets Faster...
TeoreX has announced Inpaint 6, a simple retouching tool for end users that helps remove scratches, watermarks, and timestamps as well as more complex objects like strangers, unwanted elements and... Read more
Worldwide PC Monitor Market Sees Growth in To...
Worldwide PC monitor shipments totaled 32.5 million units in the second quarter of 2014 (2Q14), a year-over-year decline of -2.9%, according to the International Data Corporation (IDC) Worldwide... Read more
Updated Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** At the Apple Store, you connect business professionals and entrepreneurs with the tools they need in order to put Apple solutions to work in their Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.