In American football, teams do not just play football. They execute predefined plays. Coaches and players do not just make it up as they go, except in “broken” plays, which are usually bad and only occasionally glorious. Indeed, the word “playbook” is common in sports. Likewise, it has a place in game AI. In fact, a book of moves is applicable to game AI beyond the sports games that require one.
At best, a book of moves encapsulates brilliant play and makes it available to the AI when conditions are right. At other times, the book can provide a selection of reasonable, if not brilliant, starting points when the cost of computing them is too high. Opening moves in Chess fit this description. A book of moves can guide look-ahead AI to search potentially fruitful paths.
The first thing we will do in this chapter is clear up any confusion between a book of moves, heuristics, and rule-based AI. Once that is done, we will examine the rationale for a book of moves, with the idea of encapsulating killer moves leading the charge. A book can provide more than killer moves; as part of a hybrid AI, we will see how a book can make it possible to have a reasonable AI at all in a complex game like Twixt. We will also show how a book of moves can empower our already effective Minesweeper AI with low-risk opening moves. After summarizing the advantages and disadvantages of the method, we have two projects: a simple book of opening moves for Fox and Hounds and a more complex one for Minesweeper.
You may be asking, “Aren’t the moves the same thing as heuristics?” You might also be wondering, “Isn’t this the same thing as a rule-based AI?” Before we dive into the details, we should shed some light on how to tell a book of moves from other AI concepts. We will compare them to heuristics first.
For our purposes, a book of moves strongly emphasizes what the AI should do. Most of the heuristics we have seen so far have been about how the AI should think. If we think back to the Fox and Hounds AI from Chapter 6, “Look-Ahead: The First Step of Planning,” we recall that the heuristics focused on the evaluation function. The way the AI distinguished between possible moves was through the evaluation function and not by anything particular to one move compared to another. If a person walked into a restaurant and told the waiter, “Bring me a taste of everything, and after I taste everything, I will let you know what I like best,” they would be using an evaluation function to decide the best move. The evaluation might be guided by heuristics such as, “Most red sauces do not agree with me.” This time-consuming and costly method of dining would be avoided if the person exploited the menu. The menu in this case is a book of moves.
The AI in Fox and Hounds would benefit from a book of moves. The first entry would be the opening sequence. Rather than looking ahead for its initial moves, the fox could simply head to square number 8, the left-most square of the third row from the top. That is the square that can force the earliest possible break in the line of hounds, and the hounds cannot do anything fatal to the fox if the fox blindly heads there. Similarly, it is difficult, if not impossible, for the fox to find itself unable to exploit any fatal mistakes that the hounds might make if the fox heads blindly for square number 8.
The distinction we are making here is not absolute. One heuristic used by the fox is close to a gray area between how the AI should think and what the AI should do. When there is an opening, the heuristic for the fox is to take the square with the lowest number. It could be argued that this is still about how the AI should think, as in, “Find the lowest number,” which is different from how it should act, which might be “Go up and to the left,” but the distinction hardly matters. Moves have an emphasis on what the AI should do, and heuristics can pertain to just about anything.
The difference between a book of moves and a rule-based system is also straightforward, although at first glance it may be difficult to distinguish between the two. Although a book of moves may lend itself to a rule-based implementation, the focus of this chapter is on hybrid AI in which the book of moves supplements a more general AI system, which need not be rule based. Our hybrid AI can “order from the menu” using the book of moves or it can “send requests to the kitchen “using the general AI. It is easy to think of the book as a set of narrowly focused, highly effective responses to specific circumstances, but they need not be that restrictive; the book can also contain typical moves that the player will expect to see. We will look at some broader, complex applications before looking in depth at how a book of moves might apply to more accessible AI. That said, rule-based systems and a book of moves are conceptually quite close, and fine distinctions between them may not be terribly enlightening.
Composers today might consider Mozart unfair competition from beyond the grave, but the truth is that anyone who can read music has full access to Mozart’s genius. Similarly, with a book of moves, game AI need not compute genius moves; it just has to be able to use them appropriately. If programmers can implement the AI equivalent to sheet music, they can then exploit any form of brilliant play they can codify. Moves tend to be specialized; Mozart’s music might not be appropriate to the instruments of a rock band. Good moves need not always be hard to find.
Imagine an in-game cut scene for the aftermath of a great battle. On one side, we see the local religious authority give the words for the living and the dead. On the other side, we see a similar figure giving similar but different appropriate words. There is no reason for the AI programmer to write either set of words; found in the back of countless hymnals and religious books are brilliant but relatively unknown writings, perfectly suitable for funerals. The selection of good words throughout the ages is rather quite rich, translation issues aside. The really old ones tend not to be familiar, making them novel when reused. As an added bonus, the copyrights on the oldest works have expired.
A similar case can be made for battle speeches, though more care must be taken:
“And gentlemen in England, now abed,
Shall think themselves accursed they were not here,
And hold their manhoods cheap whiles any speaks
That fought with us upon Saint Crispin’s day.”
The words are stirring enough, and the year it was written—1599—predates modern copyright law by a good 110 years, but the utter familiarity of the St. Crispin’s Day speech from Shakespeare’s Henry V makes it a poor choice for most computer games. The good news is that the game AI need not compute brilliance; it only needs to be able to import it and use it for its own.
All that being said, computer games lack the benefits of 3,000 years of written history and scholarship. Cutting-edge games sport novel forms of gameplay, employing rules of play that are less than two years old and known only within the development studio working on them. These rules might not stabilize until the gold master disk is burned. Where does the AI programmer get expertise when no experts exist? One potentially risky place is from early reviews of the core gameplay.
Games are supposed to be fun. Because games are financially quite risky to produce—indeed, few games break even—many studios review the core gameplay early and often to validate that the fun is there and stays there. These reviews and play-test sessions are where the earliest expertise with the game will be forged. This expertise may be rendered useless as the game evolves, but some of it may survive. Play-test sessions can be mined for good moves if care is taken from the outset. An observant set of players willing to write things down might be all that is needed. If the games are all logged and the scores are reported, promising candidates can be found and replayed for in-depth analysis. As the game develops, special AI can be used to probe and experiment. This AI need not be limited by the constraints of the regular AI; it can take longer to think or use more memory or even use a farm of machines to help. Recall from Chapter 6 that naive AI methods applied to simple games can generate run times that compare poorly to the heat decay death of the universe; no farm of AI machines is large enough to explore a space that large. For any particular new game and the studio developing it, there will be a balance point between investment and return.
A final consolation in the search for brilliance is that the AI does not have to be brilliant all of the time. As long as it is rarely stupid, the AI can thrive with occasional flashes of brilliance punctuating otherwise solid play. As we shall see, sometimes the book of moves itself enables the solid play.
Having great moves is only part of the task. The code that uses the book has to ensure that any move selected is good for the current situation. In sports, selection failures are characterized as “Good team, bad coach.” Recall Horatio, our opera singer who broke into song at a funeral? What if he was supposed to sing at the funeral? The pattern-matching problem goes from the general problem of “Do I sing now?” to the more subtle and finer-grained problem of “What do I sing now?” If Horatio has a hybrid AI, the general AI has correctly figured out that it is time to sing, and it is handing the situation off to a specialized book of moves AI for song selection. Since he is a tenor and not a baritone, he is not likely to belt out the difficult, well-known line, “Figaro! Figaro! Figaro!” But just the same, as an opera singer, his book of moves is deeply loaded with equally stunning but equally inappropriate songs. The right selection might not be Rossini or even Mozart, despite the awesome quality of their songs, but something well known from a church hymnal. The pattern-matching problems we examined in Chapter 4, “Rule-Based Systems,” are still with us.
Here, the term hybrid AI means a combination of more than one kind of AI so that the different forms mitigate the weak areas of the others. Coaches might call plays, but players execute them. The players react in real time, adjust and make changes, and do their best to exploit the unexpected. A book of moves by itself is not commonly used as a complete AI, although the line blurs in rule-based systems composed of both general rules and highly specific ones. One of the particular strengths of a book is the ability to recognize the value or peril of a situation that a more general system overlooks. We will see this in various applications.
Chess is well suited to a hybrid approach. The Deep Blue Chess computer combined powerful search capabilities with an opening book of 4,000 positions, an extended book drawn from 700,000 grandmaster games, and a database of endgames [Campbell02]. In 1997, this software, running on massively parallel hardware that included custom Chess chips, was the first Chess program to beat a reigning world champion Chess player. The evaluation function of the search was astoundingly rich, but the various books helped detect situations the search would rank improperly or spend too much time evaluating.
While interesting as a thought problem, Chess is hardly suited for programmers just starting to write AI. Games with simpler rules might appear more approachable, but it depends on the game. Go is harder for machines than Chess, but steady improvements suggest that in 20 years, machines may be able to achieve parity with professional players. The game Arimaa uses Chess pieces on a Chess board. It was specifically developed to be easier than Chess for humans and far harder for computers; opening books and endgame databases have little or no utility in a game without fixed starting positions, where all of the pieces can still be on the board at the end of the game. Twixt is another simple game that is hard for computers, but it does lend itself to a book of moves, as we shall see.
Twixt was widely published as a 3M bookshelf game, was later picked up by Avalon-Hill, and is now out of print in the U.S. The goal of the game is to form a chain of links between opposite edges of the board; one player attempts to link the top and bottom edges, while the other player tries to link the left and right edges. Links may not cross, so if one side achieves its goal, the other side is prevented from doing so. The simple rules make for complex gameplay, and draws are very rare. The game is easy to learn, hard to master, and brutally unforgiving of mistakes. Twixt is a very tactical game. One of the few strategies is to force the other side to waste one or more moves by cutting off pegs and links from the border or isolating some of the opponent’s pegs and links, preventing your opponent from connecting to other pegs and links. This strategy is hinted at in Figure 7.1, where it appears that if black makes more horizontal links in the middle of the board, black will block white from building a vertical chain to the bottom of the board. We will look at the board and see if the complexity of the game can be tamed.
Twixt is usually played on a square pegboard grid of 24 holes on a side. The opposite pairs of border rows can be played by only one color, and the corners are not playable at all. For the board pictured in Figure 7.1, white needs to connect the top and bottom, and black needs to connect the left and right. This leaves a 22 × 22 grid of 484 holes, which both sides can fill with their pegs. Pegs of the same color can be linked if the two pegs are arranged in a “knight’s move” from Chess. This is known as a “Twixt” move in Twixt. Such moves place the pegs on opposite corners of a vertical or horizontal 2 × 1 rectangle. The moves in Twixt are often denoted by the size of the rectangle they make, larger number first, so a Twixt move is denoted as a (2-1) move. Just as a knight in Chess has access to every square on a Chess board, pegs that are not a Twixt move apart can be connected by a sequence of Twixt moves if there are no obstructions. Those sequences and the art of obstructing them provide the core of the gameplay. Common sequences are known as setups, and setups make the claim, “These pegs do not connect now, but you will have a very hard time stopping me from connecting them later.”
In order to make it easier on the players, the rows and columns are often given numbers and letters to assign each hole a unique code. In Figure 7.1, there are white pegs at L8 and M10 and black pegs at N14 and P13. Another welcome addition to the original board is the diagonal lines to the corners of the open playing field, which make it easier to visualize how a race to a corner will turn out. The lines are on the same 2:1 bias that characterizes the basic Twixt move. A peg at a corner cannot be prevented from connecting to its border row. Winning the corner with a chain of links forces the opponent to block the other end of the chain or lose. Blocking an opponent’s chain from reaching its border is often done by forcing that chain against your border. This must be accomplished at the corner or before; whoever wins the corner race blocks the other. The diagonal lines make the outcome of such races easier to see. The diagonal lines also create an octagon, delineating the critical center area of the board.
There are boards of other sizes in use. An 18 × 18-hole board is less intimidating and easier for beginners as well as game AI. A quarter-size board, with 12 holes per side, is good for demonstration purposes—the Twixt resources available on the Web often make use of these smaller boards—but is too small to allow interesting play to develop.
We will start with brute-force look-ahead and then exploit the tools we have to see if we can get the complexity of the game down to something that computers can handle in reasonable amounts of time. As you might expect, the initial computations show an impossibly complex game. The goal will be to get the complexity down to something playable. To compute complexity, we will make some simplifying approximations, all based on the idea of “which is at least as big as.” If we multiply or add together simple numbers that are smaller than the actual numbers, we will get a result that is smaller than the actual complexity. Simple smaller numbers make for simpler computations. If our result using the simple small numbers is too large to be practical, then we know that the larger, actual result is likewise too large to be practical. Only when the approximation suggests that an approach might be practical will we need to use actual numbers to prove it. Approximations like these are often called “back-of-the-envelope” because they do not need a whole sheet of paper to compute them.
The naïve evaluation of Twixts computational complexity yields enormous numbers. If you could somehow fill every hole in the board, there would be 484! combinations, which is so large it is not worth computing. It is time for our first heuristic.
In a very long Twixt game, each side will make 25 moves for a total of 50 moves. Are the numbers more tractable if the search depth is limited to 25 rounds of move, counter-move? There are 484 starting moves. After taking 49 moves, we have 434 possible 50th moves. The actual complexity can be computed by multiplying the 50 different numbers from 484 to 434 together. If we approximate the 50 numbers between 484 and 434 as all being at least as large as 100, we will vastly underestimate the result, but we also get a much easier math problem.
484 * 483 * 482 ... * 436 * 435 * 434 = a very hard to compute number
100 * 100 * 100 ... * 100 * 100 * 100 = 10050 = 10100 (smaller, easier to compute)
Our approximation yields a google (a one with 100 zeroes after it). Recall from Chapter 6 that numbers this large will lead to execution times that compare unfavorably with the estimated time until the heat decay death of the universe.
Math note: 100 = 10 * 10 = 102. So with two 10s multiplied together in every 100, we get 10050 = (102)50 = 10100
Maybe some more heuristics will help. Any serious Twixt play exploits threemove combinations called setups. Not only are the setups good moves, players certainly expect the AI to use them. So if the AI wants to see the opponent’s response to its next three moves, the AI needs to look ahead six moves total instead of 50. If we again approximate the numbers between 484 and 479 as all being larger than 100 and multiply everything, we get a trillion (a one followed by 12 zeroes). The actual number is over 12,000 trillion. This number is still hopeless, but far better than a google.
484 * 483 * 482 * 481 * 480 * 479 = 12,461,242,792,078,080
100 * 100 * 100 * 100 * 100 * 100 = 1006 = 1012 (smaller, easier to compute)
Maybe we can prune. Because we are assuming that the play is based on setups, let us look at the complexity of the setups. The collection of basic setups goes in our book of moves. Once the first peg is placed, assume the best future moves are based on setups starting with that peg. Let us examine the four setups given in the original rules for Twixt. These setups, diagrammed in Figure 7.2, are known as “Beam” (4–0), “Tilt” (3–3), “Coign” (3–1), and “Mesh” (2–0). (There are other setups, including four-move and five-move setups, but these are the basic ones from the original rules.) The white pegs show the first and second moves, and the black pegs show the two possible third moves. Either third move links to both the first and second moves (known as double linking). The setups shown are for white, which wants to connect the top and bottom rows of the board.
After the first peg is placed, there are two possible follow-up moves that start a Beam (one toward the top of the board and one toward the bottom), four follow-up moves each to start a Tilt or Coign, and two for a Mesh. That is a total of 12 likely follow-up moves for the side that placed the first peg, which is far fewer than 482. If the opposition attacks the setup ineffectually, there will be exactly one move available to complete the setup. If the opposition does not attack the setup at all, there is no need to waste a move by completing the setup using either of the two available third moves, and the AI should look for the next setup that connects to this one.
What should the opponent AI do in the face of these possible setups? When possible, the most common counter is to “hammer” the first peg placed by putting an opposing peg directly adjacent to the first peg in the setup and linking to the newly placed peg. This requires that the opponent have an existing peg from a prior move that is close enough to make the link to the new peg. While the first side is setting up fancy moves, the opposing side is foiling them or cutting them off with a carefully placed Twixt move. There are at most eight holes in which to attempt to hammer the first peg, and not all of them are likely to be a Twixt move from an existing peg from a prior move. If a hammer attack is possible at all, there will usually be only a few holes that make it work. Looking for a hammer attack narrows our search for a counter-move from hundreds to a few. The hammer attack goes into the book of moves alongside the four setups.
There are 484 opening moves, and we would like to trim that number down to a more manageable number. In classic Twixt, the opening move is best placed roughly in or near the octagon created by the diagonal lines when they reach the center of the board. Opening moves here are so powerful that modern Twixt has the “pie” rule: “You cut the pie it into two pieces, and I pick which one I want.” If the opening move is particularly strong, on the second move (and only the second move) the side that did not go first can take the opening move as played as if it were its opening move and force the other side to make the second move against it by switching colors. “I’ll play your color, so that makes it your move, with you switching to my original color”. Even without the pie rule, three quarters of the opening board can be eliminated due to symmetry when looking for an opening move. If we restrict our opening moves to the 80 holes in the center octagon, symmetry reduces that number to 20, which again is far fewer than 484. We could probably get by with 10 opening moves.
With a book of moves, our AI will not search at all for an opening move. It will have opening moves that it likes in the book of moves, along with the best counter-move in case the pie rule is invoked. Some of these strong opening moves can be used as a second move against a weak opening move as well. For other moves, our search strategies will be guided by the book of moves. We avoid a general search of over 400 open holes and concentrate on the few holes that we think will matter. So how much does this improve the complexity? We might see something like the following:
One opening move (selected at random from the book)
One counter-move (based on the opening move)
Twelve holes that are a setup to the opening move
Eight holes to hammer the previous move or 12 holes to do our own setup
One or two holes to complete the setup based on the opening move, or 12 holes to do another setup
What happens when we multiply numbers like these? Our low numbers are 1 and 2; our high numbers are 8 and 12. Let us use 10 to approximate all of them and compute how expensive six moves of look-ahead would be:
10 * 10 * 10 * 10 * 10 * 10 = 106 = 1,000,000
One million is a very tractable number on current hardware. Playing by the book using look-ahead should make it possible to create a Twixt AI that is fast enough to play against, even if it does not ensure that such an AI is powerful against human players who employ four-move and five-move setups. The book of moves has taken us from “clearly impossible” to “maybe.” The code for the Twixt game shown in the figures is on the CD included with this book. Adding AI to the game is left as an exercise for the motivated reader. While the book of moves for Twixt appears straightforward, the rest of a hybrid AI that exploits that book is a daunting challenge.
The AI for Minesweeper given in Chapter 4 proved to be pretty awesome once the player got it started. So how could it benefit from a book of moves when the general rules seemed to get nearly all of the deterministic moves? One question that comes to mind is, “What is the best first move at Minesweeper?.” That question might initially get the response of “The first move is safe, so why does it matter?” But the best first move is one that either exposes the most squares or that gives the best follow-up moves when the player is forced to start taking chances. So if the first move did not expose more than one square, a good second move needs to be a move that can quickly generate the highest number of deterministic moves. We will look at the numbers and apply them to the various first moves to see if we can come up with something useful.
In Minesweeper, there are 99 mines in 480 squares. After the first move, that reduces to 479 squares. This gives a density of 0.207 mines per square on average, which is the same as having a 79.3 percent probability of being clear. These numbers are averages; the mines are not evenly spread out. We can use these numbers to give an expected value of how many mines surround a square before we click it. We will add or multiply these numbers as needed to evaluate different moves that could go into our book of moves. We will not compute the exact values of all the numbers needed to exactly evaluate the different first moves in order to keep the statistics from interfering with the analysis.
For our purposes, a middle move has two or more squares between it and any edge. As a first move, it either exposes eight more squares or presents the user with a number between one and eight. The player has a 0.7938 chance of getting lucky on his or her first move and selecting a square with zero surrounding mines. That works out to getting eight squares 15.7 percent of the time. The average yield of the first move in isolation is thus 1.26 squares. The other 84.3 percent of the time, the player is stuck making numerous risky moves to clear out an area big enough to yield deterministic moves. The problem with a middle first move is that most of the time, it gives a long series of poor follow-up moves.
There is a 0.7933 chance that a corner has no mines in the three surrounding squares. This computes to a 50 percent chance to get three squares, for an average yield of 1.50 squares, so it is better than the middle as a first move by itself. But as shown in Figure 7.3, the other half of the time it leaves the player with at least one mine to place in three squares for a typical chance of failure on the second move of 33.3 percent or worse. The corner is a good place for generating deterministic moves, but playing the corner as a first move leads to a risky second move when better alternatives are available.
There is a 0.7935 chance that a general edge square has no mines around it in the five surrounding squares. This is a 31.4 percent chance to get five squares, for an average yield of 1.57 squares, making it the best first move so far. The other 68 percent of the time, the player has one or more mines nearby, typically one or two. A second move away from the edge, if successful, can yield deterministic moves. How risky is that second move? It has a risk of 20 percent times the number revealed by the first square. Twenty percent is slightly lower than the 20.7 percent risk of a random move, so if a 1 was revealed, the edge gives safer moves than any random guess. If a 2 or higher was revealed, the surrounding squares are more risky than a random guess. The edge is superior to a corner, with higher initial yield on the first move and lower risk on the second move.
With eight surrounding squares, this kind of first move has the same initial yield of 1.26 squares that a move to the middle has if the player gets lucky. As shown in Figure 7.4, this move often creates a far better second move the 84.3 percent of the time there is a nearby mine. On average, there are 1.66 mines in the surrounding squares, making the most common revealed number a 1 or 2. A revealed 1 makes the risk on the second move 12.5 percent, almost half the risk of a random move. A revealed 2 means a risk of 25 percent. Although this is worse than the 20.7 percent risk of a random move, this is mitigated when you consider the gain of a well-placed second move. If the revealed number is less than 3, then a second move should be the neighboring square that is on the edge. There is a chance the second move will reveal a 0 and four free moves, a happy event that we will ignore for now. The second move cannot reveal a number higher than the number revealed by the first move. If the first move revealed a 1, the second move is a mine, a 0 or a 1. If these two squares leading out of an edge have the same revealed number, then there are three safe moves that “cross the T” of the first two moves. The number revealed by the second move is constrained by the number revealed by the first move, so if the second move was safe enough to take and it did not fail, it has a very high chance of giving the three free moves. The idea here is that we have created a low-risk second move with a possible three- or four-square payoff.
All the initial numbers for this case compute the same as in the previous case, but the location of the second move should be the corner. As shown in Figure 7.5, a revealed 1 means that a second move should certainly be taken. A revealed 2 is less rosy. The second move itself might reveal a 0, yielding two free squares. This configuration of a square of four cleared tiles tends to yield deterministic moves. If the second move reveals the same number as the first move, the second move generates five free moves. In either case, the resulting shape of the perimeter gives a superior board to play from. This is shown on the third board of Figure 7.5, where there is a pair of cross the T moves available for two more squares. The equally lowest-risk second move available here yields more follow-up moves and far better playing position.
An AI that computes these numbers on the fly to evaluate openings to Minesweeper would be far more involved than the AI we used in Chapter 4. It would involve both statistics as well as some look-ahead, which we covered in Chapter 6. If the exact statistics were beyond the skills of the AI programmer, Monte Carlo methods mentioned in Chapter 5, “Random and Probabilistic Systems,” could be used to home in on the right moves. None of these methods would run faster or give a better result than simply adding a highly specialized set of rules to the AI that already has the right moves coded in.
Note that we did not do the full-up, no-holds-barred statistical analysis to prove that the first moves rank in the order presented. Besides lowering the complexity of the analysis we did, this effort was intentionally skipped to let us drive the following point home: The AI does not always have to have the exact optimum move if it has moves that are good enough. Mozart might be the best great composer whose music is in the public domain, but he is not the only great composer whose music is free.
When adding a book of moves to an AI, the programmer must pay as much attention to the integration as to the parts. A good integration is seamless, making it hard to detect when the AI is playing from the book or playing from a more general method. A thin book that has a small number of stellar moves added to modestly good general AI will be obvious to the player and not always entertaining. If the player stumbles from the conditions where the AI plays using the modestly difficult general AI into the conditions where the AI plays from the expert-level book of moves, the player may feel blindsided or be convinced that the AI cheated once it saw the player getting ahead. Going the other way may not be any better, leaving the player wondering why a challenging AI decided to roll over and play dead. Thankfully, the programmer does have the option to turn moves on and off to tune the difficulty.
A book of opening moves and endgames provides a tremendous speed increase to the AI. It also can embody brilliant play and effectively leverage the play of experts. It can recognize situations that more general methods improperly evaluate. The book of moves can provide expected moves that the regular AI might miss, such as flanking or ambushing. Moves in the book can be selectively engaged to adjust the difficulty level of play. And finally, a book of moves can guide the search of look-ahead.
A book of moves is often an aid to another AI, but less often the complete AI. This can mean having two different AIs to write and maintain. The book of moves makes sense only when it is appreciably better than the regular AI it advises in some way, such as quality of play or speed. A really good regular AI might not need the book. Even an AI that needs help from the book will suffer if the expertise level of the moves in the book is not up to the task. Finding that expertise can be harder than programming it into the AI. Finally, killer moves are of no use if they are improperly employed; great plays need great coaches selecting them.
Having two AI systems means more than the effort of writing both; it means that the integration needs to be tuned as well. A “flashes of brilliance” AI can be as frustrating to the player as it is entertaining.
There are two projects for this chapter. For our first project, we will add an opening book for the fox in Fox and Hounds. Our book will have only one move, so we can hard-code the AI for it instead of using a rule-based system. Our second project is more extensive; adding a book of opening moves to Minesweeper. The Minesweeper book is nearly as easy, requiring only a modest amount of code.
Open your Fox and Hounds project from Chapter 6 or from the CD-ROM. Edit the file AI.vb and add the following region to the module between the last #End Region and the End Module lines.
#Region "Book of Moves"
Private Function ConsultFoxBook(ByVal GS As GameState) As GameState
'We only have one move in our book, only at the beginning.
'We get there on move 8, since the moves start at 0.
If GS.MoveCount > 8 Then
Return Nothing
End If
Dim bestMove As Byte = 64 'Higher than any square on the board.
Dim ss As Byte
'The fox will move up and left to get to square 8.
For Each ss In Moves.Neighbors(GS.FoxAt)
'Don't consider a blocked square.
If Not GS.HasChecker(ss) Then
'The smaller the ss the better.
If ss & bestMove Then bestMove = ss
End If
Next
Return GS.ProposeFoxTo(bestMove)
End Function
#End Region
The code is very simple and takes advantage of the way the squares are numbered. Square 8 is the first square of the third row since we start at 0 at the top left. The smallest numbered square is always above and if possible to the left. It takes the fox to square 8, but not if we forget to call the new code. Add the following lines near the top of the Fox2() function in the same file just below the initial check for a game either side has won and before where the fox gets its potential moves.
'Check the book of moves.
Dim Candidate As GameState = ConsultFoxBook(GS)
'If the book gave a move, use it.
If Candidate IsNot Nothing Then Return Candidate
You will need to comment out the declaration for the variable Candidate further down in the routine. Do this by adding a single quote character in front of the statement. The declaration comes right after a comment. After you comment out the declarations, the two lines will look like the following.
'Look at the lowest steps move as our first candidate.
'Dim Candidate As GameState
Now you can run the game and test the new code using the Fox button. See how much faster the book move is than the look-ahead? Note that the fox stops trying to go up when it gets to square number 8 or after eight moves have elapsed.
The opening moves for Minesweeper that we have discussed can be reduced to, “Click a square in a particular untouched area. If you get a 1, click a particular neighbor of that square, hoping to get a 1 or a 0.” So our book expects to have to try a first move and then a second move. Our book also expects to operate only in places where no squares have been clicked. This is different from the rule-based AI from Chapter 4 that operates only on revealed squares. This gives us two reasons not to use the existing rule-based framework for our new code. The first reason is that the existing framework doesn’t work with blank squares. The second reason is that we do not want the general AI to make risky moves unless the player directly tells it to. Since the book of moves is small and reasonably simple, we will just use some hard-coded AI. Just because a book of moves often fits very well into a rule-based approach does not mean that it always has to be implemented that way.
Open your Minesweeper project from Chapter 4. The code on the CD has an AI Auto button, and we will see it in Figure 7.6. The AI Auto button is very handy. After every book move, you should click the AI Auto button to make sure that you take any risk-free moves before going back to the book. The bulk of our code is in three routines. We need a first move routine, a second move routine, and something to execute them. We will put the move routines in the file AI.vb. Open that file and add the following code just above the End Module statement:
#Region "Book of Moves Code"
Public Function BookFirstMove(ByVal FirstSq As Square, _
ByVal SecondSq As Square, ByVal theField As PlayingField) As Integer
'Did somebody already click first move?
If FirstSq.IsRevealed Then Return 0
'First move must be unmarked.
If FirstSq.Text <> "" Then Return 0
'The follow-up move must be unmarked.
If SecondSq.Text <> "" Then Return 0
'First square needs eight unclicked neighbors.
Dim Sq As Square
For Each Sq In theField.NearNeighbors(FirstSq.R, FirstSq.C)
If Sq.IsRevealed() Then Return 0
Next
'First move looks good, try it.
theField.MoreThoughts("Book First Move attempting R" & _
FirstSq.R.ToString & " C" & FirstSq.C.ToString)
Call FirstSq.LeftClick()
'We took one move.
Return 1
End Function
#End Region
The whole point of this routine is to take a first move and second move pair and check that this is a good place to take both moves. If the first move has been taken, the square would be revealed already, and we obviously cannot take the first move again. We don’t want to take the first move if somehow somebody has already clicked the second move or marked the second move as being a mine. The code checks for the second square’s text, instead of checking to see if it is revealed. If it is revealed with no text, that means it is a zero square, and we should let the regular AI take the first move since it is free. If the second move has text, that text is either a number or a flag marker, both of which we want to avoid. For the same reason, we want all the surrounding squares not to have been clicked. We are hoping the first move reveals a 1, and for the sake of the second move we want the maximum number of squares to be available to hold that one mine, minimizing the chances that the second move is the one holding it. If the square meets all our needs, we click it (and hope).
The first move is a risky move that usually does not tell us a whole lot. The second move is likewise risky, but hopefully it tells us something useful. Add the following code to the same region:
Public Function BookSecondMove(ByVal FirstSq As Square, _
ByVal SecondSq As Square, ByVal theField As PlayingField) As Integer
'Take the second move if the first move looks good.
'First move has to have revealed a minimally risky number.
If FirstSq.Text <> "1" Then Return 0
'First square needs eight unclicked neighbors.
Dim Sq As Square
For Each Sq In theField.NearNeighbors(FirstSq.R, FirstSq.C)
If Sq.IsRevealed() Then Return 0
Next
'First move was perfect, attempt the second move.
theField.MoreThoughts("Book Second Move attempting R" & _
SecondSq.R.ToString & " C" & SecondSq.C.ToString)
Call SecondSq.LeftClick()
'We took one move.
Return 1
End Function
The second move code has the same idea: Make numerous checks and, if they pass, take the second move. The first move has to have shown a 1. The surrounding squares have not been revealed, so the one mine has the lowest probability of being on the second move’s square. If that is the case, the second move is worth taking. Now we need to code to execute these first and second moves.
Switch to the file PlayingField.vb. There is a code tab and a design tab; we will do the code first. Find the AI Related region and add the following code to it:
Public Sub ExecuteBook()
'Store the pairs of moves in collections.
Dim FirstSquares As New Collection
Dim SecondSquares As New Collection
'Add in pairs of moves to the collections in order.
'Add in the corners first.
'Add the upper-left corner.
FirstSquares.Add(Field(1, 1))
SecondSquares.Add(Field(0, 0))
'Add the lower-right corner.
FirstSquares.Add(Field(NumRows - 2, NumCols - 2))
SecondSquares.Add(Field(NumRows - 1, NumCols - 1))
'You can figure out from here how to add the other two corners.
'Then add some edge moves, from center outward.
Dim Col As Integer
For Col = 1 To NumCols 4
'Add moves on upper edge going right.
FirstSquares.Add(Field(1, NumCols 2 + Col))
SecondSquares.Add(Field(0, NumCols 2 + Col))
'Add moves on upper edge going left.
FirstSquares.Add(Field(1, NumCols 2 - Col))
SecondSquares.Add(Field(0, NumCols 2 - Col))
'You can figure out how to add the lower edge.
Next
'If we wanted the left and right edge, we'd add them here.
'Now walk down the list in two passes.
Dim pass As Integer
For pass = 1 To 2
Dim FirstMove As Square
Dim SecondMove As Square
Dim i As Integer
For i = 1 To FirstSquares.Count
'Get the first and second moves out of the collections.
FirstMove = FirstSquares(i)
SecondMove = SecondSquares(i)
If pass = 1 Then
'Check for follow-up moves first; they pay off better.
If BookSecondMove(FirstMove, SecondMove, Me) > 0 Then Return
Else
'Look for first moves.
If BookFirstMove(FirstMove, SecondMove, Me) > 0 Then Return
End If
Next
Next
End Sub
That chunk of code can be divided into two parts. The first part collects the pairs of first-move and second-move squares and stores them in the order we want them checked. It does the corners first and then the edge moves. The edge moves concentrate on the middle of the edge, hoping for a good breakout pattern in three directions. We include only two of the four corners, and we do only the top edge. If we try all four corners, there is a non-trivial chance that our code will hit a mine near a corner before it tries an edge move. For the sake of instruction, we want a good chance at seeing the code take multiple book moves before hitting a mine. All these moves are low risk, but none of them are risk free.
The second part of this code loops through the pairs of moves in order, stopping as soon as one of them executes. Notice that it looks for second moves in the first pass before it looks for first moves in the second pass. This is not a coding error. The second move is the one most likely to net us deterministic safe moves. We take the risk of the first move only so that we can execute the second move and make some headway. So we always check for moves we want to take before we resort to moves we have to take. In any case, since the code takes only a single move before it chickens out, it has to check for second moves first; otherwise, it will risk every possible first move in the collection before doing a follow-up second move. On any run of the code, the code does not know what first moves have been taken. Even if the AI kept track of first moves that it took, the player could have taken some first moves that the AI would not know about, so we always check to make sure.
All we need now is some user-interface code to enable the user to try these risky moves. Switch to the design view of PlayingField.vb and add a button. Change the name of the button to BookButton and the text to AI Book. Set the enabled property to false. (Figure 7.6 shows the button in place.) Then switch back to the Code view and add the following code:
Private Sub BookButton_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles BookButton.Click
'Make sure the book button gets enabled and disabled.
FirstThought("Executing from the book of moves (could be risky!)")
Call ExecuteBook()
End Sub
All that remains is a few details. Add the following line of code to the EndGame() routine:
BookButton.Enabled = False
Add the following line of code to NewGame():
BookButton.Enabled = True
Now we are ready to test. Run the code and start an expert-level game. Click the AI Book button until the AI hits a mine or until it successfully executes a second move. Let the regular AI take over if it can. If the regular AI gets stumped, go back to the AI Book button.
With a new game, see if you can click the AI Book button enough times that the AI runs out of book moves to attempt before it hits a mine. This may require you to run a large number of failed games before it happens. This illustrates why we did not add all the possible combinations to the collections; it will be rare to exhaust them all without gaining some traction for the regular AI. This can be seen in Figure 7.6. Note the every-other pattern you get on the top row. The book of moves won’t attempt adjacent squares, so it skips a square. If the book finally gets in a second move, this every-other pattern gives the regular AI a fighting chance to make additional moves via RuleTwoFar in the regular AI.
Our hybrid AI has a reasonable opening book and a very solid rule-base for general play, but it lacks an endgame AI. Endgame in Minesweeper often boils down to, “You have to make N fifty-fifty guesses to complete this board.” Our code demonstrates how a book of moves can provide a powerful adjunct to a good AI, but there is no book of moves, and there are no general rules that will help when it comes down to just guessing.
A book of moves can make all the difference in a game AI. It can improve the speed or quality of play that the more general methods provide. A book is very good at providing the player with expected actions from the AI. When backed up by a good general AI, it need not have the perfect move for every occasion. It makes demands on the programmer, especially when used in games with completely new gameplay.
Answers are in the appendix.