Chapter 9 - Strategy

This chapter is a bit of a hotch-podge. There is no easy classification of this group of games as they cover everything from Ludo to Cribbage. These are the more static games, sometimes known as parlour games . Here the ability to think many moves ahead is far more important than speed, and this is reflected in a rather different way of using the computer. All the real work is done when nothing is happening on the screen. Such games are likely to be far more amenable to multi-tasking. This is in contrast with arcade games where everything has to happen very rapidly in parallel. Again, the fact that the player will be staring at the display for long periods means you will have to devote a great deal of time to producing a polished but uncluttered layout.

9.1 Algorithms and Rules

Before you can make any progress with this class of game you need to develop a clear understanding of the rules that apply to the game and turn these into a precise methodology of implementing them. In other words - the algorithm. Attempting to build this kind of game piecemeal is a certain recipe for disaster. I have to confess that this is a lesson that I learned the hard way some years ago on my first attempt at the Othello board game.

9.1.1 Regional variations

The older and better known a game is the more variations you are likely to come across. You must therefore try to find out as much about the regional differences as possible and provide the facility for players to select which variant they wish to play. Ideally you should give them the option of saving their preference to disk so that they don't need to set the options each time they play.

Two games that come to mind where this is particularly relevant are Patience and Draughts. There are so many variations in Patience that, unless you're going to write a particularly unusual form, you may decide to avoid the game altogether! However, in the best known seven column form there are a number of major differences that you can easily accommodate. A few of these are listed below.

• Permit any picture card to be placed in any empty column;
  
• Shuffle remainder stack each time it has been worked through;
  
• Allow only one pass through the stack;
• Allow ordered cards to be split and moved from one line to another.

The problem with Draughts is the huffing rule. You will find that this is quite hotly contested as to whether it should be applied or not, so if you're programming draughts do make sure you provide huffing as an option. The fragment below show how easy this is to implement.

IF cantake% AND huffrule% PROCtest ELSE PROCmovepiece

There is a very obscure variant of this that changes the strategy of the game quite significantly. One player sets up a double huff situation, so that the opponent has two choices where a piece has to be taken. Whichever choice is taken, a huff is called on the other option, resulting in a guaranteed loss of one piece each.

9.1.2 Symmetrical Patterns

When working out algorithms for strategy games it is easy to forget that you often have a symmetrical layout, and that many possible moves are simply mirror images of each other, particularly where opening strategies are concerned. An example of this is Noughts and Crosses, or Tic-Tac-Toe. If you look at figure 9.1 you will see that three squares are shaded. These are the only starting locations your program needs to consider. All the other positions are rotations or mirror reflections of these positions. As a result you can examine the opening move completely with only three sets of calculations instead of nine.

If the computer makes the first move then it is easy to arrange for apparent changes in opening strategy by randomly selecting the other images of these starting locations. The fragment below shows how this can be done using the box numbers of Figure 9.1, although I wouldn't normally recommend such an inefficient way of doing it.

IF select%=5 THEN
 
ELSE
 rotate% = RND(4)*2
 IF select%=1 THEN rotate%-=1
 IF rotate%=5 THEN select%=9 ELSE select%=rotate%
END IF

The position becomes only slightly more complex if the computer makes the second move. In this case, after rotating the player's move to the form we recognise, you take the diagonal through 1,5,9. The computer's response can then be reflected either side of this axis. Here you will find there are a possible five positions to be examined rather than eight.

With a game as simple as this, with so few possible combinations, it is a practical proposition to directly specify a fixed set of rules defining how the computer should respond. However, this is not normally the case.

9.2 Recursive Computer Moves

Mention recursion to many people and they go weak at the knees. This is because the concept is rather alien to our normal straight-line style of thinking. Instead of a linear progression of tests and action with recursion you perform a few tests, hold the results and perform another similar set of tests, and repeat this activity, maybe many times, then piling tests on top of groups of tests, until you eventually have a possible best action. This kind of mental juggling, keeping so many balls in the air, is very difficult for most people. However the rules for recursive code are usually quite simple, and it can be very satisfying to watch the computer wind up a recursive problem then adroitly unwind with a solution.

One point to watch very carefully with recursion is that you always have an exit point. You will see this in the pseudo code example below for a four in a line type game. The recursion entry is only made after all possible terminating conditions have been tested. The second test is remarkably easy to forget.

Recursion entry;
   If this move completes a line, store move details and exit;
   If no more moves possible, set flag and exit;
   Swap opponent with computer and call recursion entry.

9.2.2 Minimaxing

The concept behind recursive algorithms is quite straightforward. The computer finds the first valid position for its next piece. It tests to see if it is a winning move, and if not it checks to see if the move could give the opponent the winning move. The computer then checks to see if any of the opponent's possible responses could provide a winning computer move at the next level. If the move looks dangerous then the computer will try the next valid position, until either a winning position has been found or all positions have been investigated. In the latter case, depending on the precise algorithm, the computer will either chose the move that is likely to produce a win for itself in the least number of moves or takes the most number of moves to allow a win for the opponent. This latter option, could produce a computer win if the human player makes a mistake.

This searching out best or computer maximums in parallel with worst or opponent minimums, called minimaxing, can make huge demands on processor time. In most games any move made will give a large number of choices to the opponent and if all of these are investigated you will see that the number of tests made rapidly expands in a tree like structure until it becomes impractical to continue.

9.2.3 Limiting Recursion

What is needed, therefore, are methods of limiting the number of tests that are made recursively. The first, and most obvious way of doing this is to control the number of moves the computer looks ahead. This simply involves the use of a counter to control the recursion depth. Putting this under player control can be used to give coarse difficulty settings.

A similar, but subtly different solution is to limit the time the computer can take following any one recursive path. Where the former method gives a fixed cut-off point regardless, using time as the limiting factor enables a promising line of moves to be investigated more thoroughly.

9.2.3 Pruning

A common technique for time saving is to do some tree pruning. If you are looking for maximums and branch A has leaves that produce the values 2, 7, 8 and 6, but the first leaf of branch B produces 9, you don't need to bother to check any other leaf of branch B as you know that at least one route in the B branch is better than any in the A branch. You still need to check branch C however, unless branch B produced the maximum value possible. If branch C produces a higher value than B then you will have to go back and check the remaining parts of B to see if it will again yield a better value. This is shown in Figure 9.2.

Note that the pruning attempt of G is not valid. It is easy to become confused here, but as a general rule you can't prune if it's the first branch as there is no earlier one for it to be better than.

Had C given a result of 11 from its first leaf then you would go back to B and look at the I leaf. If this was greater, say 15, then you wouldn't bother with J but would go back to looking at L. In the worst case, with L producing 15 or more, you would then go back and examine J. All this swapping backwards and forwards may seem wasteful, but I've given the worst case situation, usually there are considerable savings to be made.

9.2.4 Fuzzy Thinking

Many games have more than just simple good or bad moves. With these, if you keep a numerical count of the quality of the moves you can develop a strategy of progressively ignoring the more unlikely situations the deeper you go recursively, only stopping at the point where no further conditions are tested at all. This will speed up calculations and give a sort of fuzzy edge to the computer's thinking. This may not make a particularly smart machine game, but it will make it harder for an opponent to predict. This in itself can make a game far more attractive and seeming human. Many people believe that the computer can't make mistakes. They will relax if they see it make a move that they know can be bettered.

9.3 Weighting Schemes

Using recursion is not the only way you can produce an intelligent machine gameplay, and indeed not the first that most people think of. Instead of just totalling the number of pieces taken and the potential gains from the later moves you can maintain a board array with the weighting values for the various positions. Where you have more than one valid position you should perform a limited recursive scan to find the most advantageous moves. After this you apply the weightings to modify the 'best' positions, possibly at the cost of actual pieces at this level. This can become very complicated so you need to strike a balance between improved machine intelligence and complexity. With the simpler games it may be possible to produce a weighting scheme that is good enough to be able to do away with recursion altogether.

9.3.1 Key Moves

An example of the way you can improve machine intelligence can be shown with the game Reversi or Othello as it is sometimes known. If you only use recursion to pick the best moves then you may need to wait a long time going to the depth necessary to beat an experienced player. However, when you examine the game you see that there are a number of key positions that can greatly enhance your chances of winning.

The most obvious ones are the four corner positions. Pieces placed here can't be taken so unless the opponent uses some pretty fancy strategy whole lines can be controlled from the corners. This is particularly true if you command two corners on the same side of the board.

In Figure 9.3 there is one possible set of weightings for the Othello board. The numbers only provide a guide as to the importance of the positions, not an absolute value. You will notice that I've given the squares adjacent to the outside squares the lowest values. If you put a piece in these squares you are letting your opponent get to the outer edge and possibly the commanding position of a corner. Finally, you can make your weightings dynamic and adjust them as a game progresses to reflect the changing status of certain moves or positions.

9.3.2 Randomising

If possible keep your opponent guessing. Where there is little significant difference between two or more moves don't make the mistake of always choosing the first. The player will eventually be able to follow the pattern that the machine plays and so beat it every time. Instead, make a random selection, even allowing slightly less advantageous moves to be made in the earlier stages.

9.4 Introducing Othello

Many games can be reduced to a few simple rules. Looking at Othello in more detail we first need to establish the starting conditions. it's easy to forget that the starting moves may be quite different from any others. It is a common mistake to try to make the main game loop include starting conditions. This is error prone, and slows the program down. It's usually far simpler to have a separate routine.

   The game is started with the first four pieces already placed in the central four squares with the colours lined up on the diagonals.

Now you can specify the rules for valid moves. This should always be separate from the main move calculations for two reasons. First a quick scan for validity saves time if the move is invalid. Second the same checking routine can be used for both computer and player moves.

• Every piece must be placed within the 8 * 8 grid;
  
• Every piece must be placed adjacent to at least one opponent's piece;
  
• There must be a players piece beyond and adjacent to the opponents piece or line of pieces in at least one direction;
  
• If a piece can't be placed the move is forfeit;
  
• If a piece is wrongly placed the move is forfeit (optional).

Once a valid move has been found the following rules can then be applied to develop the game strategy.

• All pieces have the same value;
  
• Board positions have a weighting value;
  
• A move that increases the players piece count is a potential good move;
  
• A move that gives the opponent a chance to increase his count may be bad
  
• A move that reduces the opponents piece count to zero is a winning move;
  
• A move that allows no more moves to be made closes the game.

The first rule is easy to overlook. In a game like Chess pieces have very different values in a weighting scheme, but board positions would become less important.

The last two rules inter-relate in that the capturing the opponent's last piece automatically makes any further move invalid for either player. It is important to be clear about winning moves. The routine you use must always be able to spot these, and then ignore all other moves. At the same time you mustn't confuse a winning move with one that leads to a win.

In this game, particularly in the early stages, a move that gives the player more pieces is not necessarily a good move. Similarly a move that allows the opponent to take pieces may not be a bad move. In a game where pieces could only be captured once this would be true, but in Othello an individual piece can swap colours many times. The unfortunate result of this is that tree pruning is most unwise. Recursion limiting should be done with a combination of recursion depth and key move testing, using board weighting to evaluate key moves.

9.5 Card Games

Unfortunately most multi-player card games are impractical as there is no way of preventing your opponent from seeing your cards. You could develop a game using two machines, linked via their serial ports, but there would be little demand as not many people can justify two computers. However, games played against the computer are practical as people readily accept the idea of a computer player not being able to see your cards while the computer referee sees all of them.

9.5.1 Displaying a Hand

One difficulty that arises when programming card games is the matter of displaying a large number of playing cards in such a way that they are clearly visible and yet all fit on the limited screen area in a reasonable pattern. While you can gain space by overlapping cards in the same way as a player normally does with a hand this still can leave you short of space.

If you intend your game to work within the desktop you can circumvent this to some extent by using scrollable window and only display about half the cards. If you do this you must give the player the option of re-ordering the cards, exactly as he or she would with a real hand of cards. Actually, I recommend using the desktop and then defining the cards as sprite icons. This makes selection and dragging remarkably easy as the WIMP does most of the work for you.

If you're not working within the desktop then you will either have to reduce the size of the playing cards, which will reduce their detail and attractiveness, or display the cards in blocks. These can then be flicked through with say, Select and Adjust mouse clicks. I would recommend using simple sprites rather than drawn cards. If you want to add a bit of style you can have an animated film of the cards being bent as they are placed, synchronised with a suitable sampled thwack.

9.5.2 Patience Layout

Figure 9.4 is a specimen layout for seven card patience. It looks a bit sparse but will quickly fill out as the game progresses. For simplicity I haven't bothered with detail on the card faces. The background should ideally be a dithered green, to give a card table appearance. The plinths for the stack, and the piles, could either be tinted for a metallic effect, or better still, given a wood grain appearance.

You will see that card edges are shown to give an indication of the number of cards that are in the piles. This is particularly relevant for the laying out columns, as there is unlikely to be enough room to show the reversed cards spaced down as they normally are, along with the visible cards.

Assuming a mouse driven game everything needed is visible. Cards would be selected by dragging. The game can be re-started by clicking on the New icon and the program abandoned, returning to the desktop, by clicking on the Quit icon. You could easily add another two icons to Load and Save the game.

9.5.3 Implementing Patience

It is useful to have a brief look at the game itself from a data structure point of view. You need to know how many cards are in each of the columns, whether they are visible or not, and what the cards are. In the stack you need to know how many cards are in the unused section and how many in the used section and their values. With the piles you only need to know the number of cards in each pile. Logically you know the top card of each pile as they are in numerical order.

The stack can easily be held as a pair of arrays. As 28 cards are already placed in the columns the array sizes only need to be 24. The zero element can be used to indicate the number of cards in the stack, or more specifically, the pointer to the next card to be handled, while all the other elements are actual card values. As the stack is handled three card values are moved from the unused stack to the used stack and the pointers updated. As cards are lifted from the used stack it's pointer is simply decremented. When the entire stack has been seen a simple swap of the contents, remembering to reverse the order, is all that is needed.

Columns are also best implemented as arrays. This time the array size has to be 17. This is to allow for the unlikely possibility that the first column while still with seven cards will have the whole of an ordered line on top of it. This time you need to maintain two pointers per array. The zero element can again be the pointer to the last card. However, you also need a pointer to the first visible card or last hidden card, whichever is most convenient.

Finally, the ordered piles can be simple integers with a card count. When the sum of these integers is 52, then the game has been successfully completed.

9.5.4 Shuffling

One common mistake with card games is shuffling the pack. I've seen some of the most horrendous and convoluted routines that try to find random numbers between 1 and 52, then check they haven't already been selected, place them in an array and increment a counter. If you think about it you will realise that it is far simpler to shuffle your array in exactly the same manner as with real cards.

First fill it linearly with the numbers 1 to 52 using a FOR NEXT loop. This takes care of the problem of ensuring that there are no repeats. All you need do now is randomly select array positions and swap their contents. To get a good shuffle you need to perform about twice as many swaps as there are items in the array, 104 in this case. You don't need to prevent your random selections repeating the same swaps. As with real shuffling moving a card out of a position and then back again is quite valid.

An identical method can be used for similar counted choices such as shaking the bag for a Bingo session or mixing up Dominoes before laying them out.

9.6 Tile Based Games

This sub class covers quite a wide range and includes Dominoes, Mah Jong and Scrabble. The problems here are not so much that of display but orientation and matching. Having said that, Mah Jong tiles can take up a lot of space.

Taking Dominoes, for example, you need to establish not only which Dominoe is being handled but also its orientation and the orientation of the Dominoes already laid. This is of particular importance with the " Fives and Threes" game, where both you and the computer will want to maximise your fives and threes count. In this case you not only need to know that a match has been made, but also the total spot count. This has to be a multiple of five or three to score.

Probably the simplest way of handling this sort of problem is by using a two dimensional array for the Dominoe stacks of both players. For the Dominoes already laid you only need to keep a record of the two end points. For convenience these could be marked with two variables that would be set to spot count of the ends of first Dominoe placed. From then on they would be set to the free end of each Dominoe placed at that position. Below is a list of the type of tests that you would need to make for this.

• Does Dominoe left end match stack left end;
  
• Does Dominoe right end match stack left end;
  
• Does Dominoe right end match stack right end;
  
• Does Dominoe right end match stack right end;
  
• Does left placing give 5 or 3;
  
• Does right placing give 5 or 3;
  
• Does left placing give higher 5 or 3 than right placing;
  
• Is this the highest scoring Dominoe.

These test would be in addition to the normal strategy assessment for obstructing the opponent and maximising the options for placing all Dominoes.

9.7 Word Games

Although many word games fit in the sub-class of tile games by virtue of the orientation and matching necessary for individual letters and words the core of this type of game is the dictionary. There are public domain dictionary utilities available but you can generate your own without too much difficulty.

Initially you can use a system similar to that suggested for adventure games, where you have a simple array holding a list of words. You then scan this for a match with the word being tested. However, this becomes impractical with a dictionary of any size. The solution, in part, is to use a binary search.

9.7.1 Binary Searching

For this, it is essential that the word list is in alphabetical order. As you don't want to waste time with sorting algorithms the most practical solution is to ensure that the dictionary is alphabetically ordered in the first place.

For the actual search you start by dividing the word list in two and then compare your word with the one in the middle of the list. If it matches, you flag it accordingly, otherwise, if it is alphabetically lower you repeat the operation with the bottom half of the list, while if it is higher, you work on the top half. This is repeated until either the word is matched, or the list can't be split any further.

9.7.2 Text Compression

Another way you can increase the response time of your dictionary is by using text compression, making the strings to be compared shorter and also reducing memory requirements. Incidentally, this is again applicable to adventure games.

The byte-by-byte representation of characters in strings is very wasteful. Out of a possible 256 values you only use 26. These can be represented in only five bits instead of eight. This fact is used in listing 9.1 which times the difference between compressed and non-compressed binary searching.

REM > Dictionary
:
PROCinitialise
:
REM   test routines
:
PRINT''"Sorting normal  Time = ";
TIME=0
PROCsort(word$())
PRINT;TIME
:
PRINT "Sorting packed  Time = ";
TIME=0
PROCsort(pack$())
PRINT;TIME
:
a$=word$(103)
p$=pack$(103)
PRINT''"Performing searches ";N%+1 " times"
:
PRINT'"Searching normal  Time = ";
TIME=0
FOR I%=0 TO N%
f%=FNmatch(a$,word$())
NEXT
PRINT;TIME
:
PRINT "Searching packed  Time = ";
TIME=0
FOR I%=0 TO N%
f%=FNmatch(p$,pack$())
NEXT
PRINT;TIME
END
:
DEFPROCinitialise
wordnum%=999
DIM word$(wordnum%),pack$(wordnum%)
N%=499
a$=STRING$(16,".") : REM fixing string lengths
b$=a$              : REM speeds up swaps
MODE 12
PRINT''"Generating ";wordnum%+1 " dummy words - Please wait";
FOR I%=0 TO wordnum%
word$(I%)=a$
word$(I%)=FNline
pack$(I%)=a$
pack$(I%)=FNpack(word$(I%))
NEXT
ENDPROC
:
DEFFNline
LOCAL I%,a$
FOR I%=0 TO 4+RND(5)
a$+=CHR$(64+RND(26))
NEXT
=a$
:
DEFFNpack(a$)
LOCAL s%,d%,b$
REPEAT
PROCget
d%=s%
PROCget
d%=d% OR s%<<5
b$+=CHR$ d%
d%=s%>>3
PROCget
d%=d% OR s%<<2
PROCget
d%=d% OR s%<<7
b$+=CHR$ d%
d%=s%>>1
PROCget
d%=d% OR s%<<4
b$+=CHR$ d%
d%=s%>>4
PROCget
d%=d% OR s%<<1
PROCget
d%=d% OR s%<<6
b$+=CHR$ d%
d%=s%>>2
PROCget
d%=d% OR s%<<3
b$+=CHR$ d%
UNTIL a$=""
=b$
:
DEFPROCget
s%=ASC a$-64
a$=RIGHT$(a$,LENa$-1)
ENDPROC
:
DEFPROCsort(word$())
LOCAL a$,a%,b%,n%
n%=DIM(word$(),1)
PROCqsort(0,n%)
ENDPROC
:
DEFPROCqsort(s%,e%)
IF s%>=e% ENDPROC
a$=word$((s%+e%)>>1)
a%=s%-1
b%=e%+1
REPEAT
REPEAT
a%+=1
UNTIL word$(a%)>=a$
REPEAT
b%-=1
UNTIL word$(b%)<=a$
IF a%<b% SWAP word$(a%),word$(b%)
UNTIL a%>=b%
PROCqsort(s%,a%-1)
PROCqsort(b%+1,e%)
ENDPROC
:
DEFFNatch(a$,word$())
LOCAL s%,e%,h%,f%
e%=DIM(word$(),1)
REPEAT
PROCbin(s%,e%)
UNTIL f%
=f%
:
DEFPROCbin(s%,e%)
IF e%>=s% THEN
h%=(e%-s%)>>1
IF a$>word$(s%+h%) THEN
PROCbin(s%+h%+1,e%)
ELSE
IF a$<word$(s%+h%) THEN
PROCbin(s%,e%-h%-1)
ELSE
f%=s%+h%+1
ENDIF
ENDIF
ELSE
f%=TRUE
ENDIF
ENDPROC

A list of random words of eight characters average length is first generated. At the same time a compressed copy of each word is produced by FNpack. As it stands the routine assumes that all characters are upper case letters.The two lists are then sorted with a quicksort routine and this is timed. Finally the two lists are searched for a string known to be at position 103. This value is chosen to reduce the possibility of unnaturally fast binary divisions occurring.

You will see that the search is in fact extremely fast. It needs 500 iterations to get a meaningful timing. What is even more impressive is that if you increase the word list to 10000, the generating time is several minutes, and the sorting time slows considerably too, but the search time is hardly affected. Also the larger the number of words, the more reliable the time differences become. With 10000 words, both sort and search times are about 10% faster using packed words, and the memory saving is around 25%

9.7.3 User Dictionaries

One problem with word games is the fact that your dictionary will be incomplete. Therefore you should make some allowance for additions to be made. A simple solution is to maintain a text file of additional words. This is built up by the game itself in response to unmatched words and, the next time the game is played is loaded into a separate array at the beginning of the game. As the players are likely to generate a much smaller list than the main dictionary you can probably get away with a simple linear search for this list. If new words are added as the game progresses a flag should be set, and when the game closes the player should be offered the choice of saving the new additions. To avoid, the interruptions caused by continual requests for confirmation that a new word has been entered your game could have a switchable learn mode. For normal play, this can be disabled so that the computer can respond quickly to wrong spellings.

9.8 Strategy in 3D

A few games, such as Noughts and Crosses, have been revamped with three dimensional implementations. This can make an otherwise dull game considerably more exciting. Theoretically almost any two dimensional board game can be made three dimensional. However, I'd hate to try to play 3D Chess.

In principle all you need do is add an extra dimension to the board array and another counting loop in the move validation and computer. However all calculations will now take very much longer. So much so that a computer-human game may not be practical and you may have to satisfy yourself with human-human implementation.

Unfortunately many programmers shrink from a true 3D layout and just place a group of boards alongside each other. This not only detracts from the game play but also significantly changes the difficulty of the game. In some cases it makes it easier, in others harder. Using the perspective ideas in chapter 6 you can draw a board relatively simply and, if you prefer, use scaled sprites for the pieces. To give the player more control you can also use the 3D rotation formulae so that he or she can view the game from any angle.

The easiest way to produce an unambiguous display is to use different tints for the pieces on different levels. Logically you would use the darkest tint for the lowest board. Taking 3D naughts and crosses as an example all four boards can be uniquely identified. If you have more than four layers then you will need to use combinations of colours and tints that show an obvious progression. This is quite easy in the 256 colour modes if you refer back to my earlier suggestion of selecting colours bit-wise.

If you are using the mouse to pick up pieces, which is almost essential, you should use inverse video or switch to flashing colours to highlight the piece that the mouse is over. As you move the mouse the piece should follow it in jumps, always staying clearly placed within the playing grid.