Diplomacy Zine -- EP #211 Chapter Seven From: Eric_S_Klien@cup.portal.com Date: Sat, 10 Nov 1990 00:19:47 +0000 Issue #211 of ELECTRONIC PROTOCOL: **************************************************************************** I think that, in the interest of honesty, the government ought to pass a law requiring companies to use regular Earth people in their commercials. Here's how they would behave: COMMERCIAL FOR WISK (Two men are talking at a party, as their wives listen.) First Man: I'm feeling really wrung out lately. Second Man (jeeringly): That's because you've got ring around the collar. Ha ha. (The first man shakes his head sadly, then walks off.) Second Man: What's with him? Second Man's Wife: His mother just died, you idiot. -- Dave Barry, "Subtracting the Ads" **************************************************************************** Chapter One contains: BAGHDAD, AUSTERLITZ, BLITZKRIEG, KING'S GAMBIT, PASSCHENDAELE, GET SOME, DRAGONS, BLACK OCTOBER And is published by uunet!cti1!rlister or rlister@cti.com/Russ Lister Chapter Two contains: REPUBLIC, BORODINO, JACAL, VERSAILLES, DRESDEN, KHAN And is published by sinhaa@mcmaster.ca/Anand Sinha Chapter Three contains: DAWN PATROL, BERLIN, EL ALAMEIN, SQUALANE, UNGAWE, BRUSILOV OFFENSIVE, CULLODEN, GANDALF'S REVENGE, GOODBYE BLUE SKY And is published by cwekx@htikub5.bitnet/Constantijn Wekx Chapter Four contains: OZARK, DEADLY DAGGERS, YORKTOWN, MONTREUIL-SUR-MER, FIRE WHEN READY, THUNDERDOME And is published by dm8sstaf@miamiu.bitnet/Douglas M. MacFarlane Chapter Five contains: DEF CON 5, BORDEL, ERIS, MASADA, YALTA And is published by jjcarette@watami.waterloo.edu/David Gibbs Chapter Six contains: TOKUGAWA, BERLIN WALL, HIROSHIMA, GENGHIS KHAN, SEA LION, VIOLENT PEACE And is published by ps9zrhmc@miamiu.bitnet/Peter Sweeney Chapter Seven contains: HELM'S DEEP, GROUND ZERO, GIBRALTAR, TIBERIUS, BETELGEUSE ------------- Chapter Seven ------------- Table of Contents: Answers to Quiz from EP #204 A Defense of F Sev H by Robert Sergeant On the drawbacks to F Sev-H: A reply to Bob Sergeant By Mark Berch New Quiz by Daniel Loeb A letter from chbrin5@dknkurz1.bitnet/Kai Hortmann Amid The Taxfest, Spending Cuts Are Rare from Investor's Daily Thoughts on Programming a Diplomat By Michael R. Hall -- Part One ---- >*****************************************************************************< ANSWERS <*****************************************************************************> The following are three correct answers to the quiz published in EP #204: In that quiz, Danny asked if you could color the Diplomacy map using red, white, and blue without two adjacent provinces having the same color. From: "Matt Crawford" <matt@oddjob.uchicago.edu> That is, can the diplomacy map be colored red, white, blue without having two adjacent provinces with the same color. If yes, then how. If not, then how about if we define "adjacent" as "adjacent for a fleet" or "adjacent for an army". No, the diplomacy map cannot be three-colored in any of these cases. Proof: Assume the map can be three-colored. Case 1 -- general adjacency Sweden and St. Petersburg must be the same color, otherwise Norway and Finland would use up the third and need a fourth color. So wlog color Swe and StP red and Finland white. Then GoB must be blue and Lvn white. Now there is no color left for the Baltic. Case 2 -- considering adjacency for fleets only NAt and Eng must be the same color, otherwise Iri and Mid would use up the third and fourth colors. So color NAt and Eng red. Nwg and Nth must be different colors and not blue, so let them be white and blue, respectively. Now Edi must be red, and Lvp white. What color is London? Case 3 -- considering adjacency for armies only (without convoys, of course, or even four colors would not be enough!) Start with Mar and Par, which must be the same color because of their adjacency to Gas and Bur. Let Mar and Par be red, Gas white, and Bur blue. Then Bre must be blue, Pic white, Bel red, Ruh white, Hol blue, and Mun red. No color is left for Kiel. From Kai Hortmann/chbrin5@dknkurz1.bitnet: No, the diplomacy map cannot be colored in only 3 colors, not even with the redefinition of "adjacent". Proof: Take a province with an uneven number of adjacent provinces that completely circle the province, e.g. Bohemia for armies or the Tyrrhenian Sea for fleets. You have to choose one of your three colors for it. Lets call it color 1. Now take one of its neighbors. You will have to give it a different color, lets say color 2. Now choose the next neighbor, clockwise or anti-clockwise. As this is bordering the original province (color 1) and the first neighbor (color 2) we will have to give it color 3. The third neighbor is color 2 again. The fourth is again color 3. Now what color do you choose for the fifth and last neighbor? This borders the original province (color 1), the first neighbor (color 2) and the fourth neighbor (color 3). You need a fourth color there. <* Kai Hortmann - chbrin5@dknkurz1.bitnet - Konstanz - Germany *> From: Jamie Dreier <PL436000@brownvm.brown.edu> Eric; Here is my preliminary solution to Loeb's question about 3-coloring the diplomacy map. I may want to add something later. ------------------------ Danny's problem about "tricoloring" the dipmap is another gem. Fortunately, it's a good bit easier than his earlier problems! The answer is that one cannot tricolor the map, even separately for armies and fleets. A subproblem is, what are the smallest neighborhoods that cannot be tricolored for fleets, and which are the smallest for armies? I believe I have the answers. For armies there are five "nontricolorable" neighborhoods of 6 regions each, and for fleets there are three. Each neighborhood has the structure of a ring of five regions arranged around a central region, thus: ___________________________ : \ / : : \ / : : \ _____/ : : / \ : :______ / \________: : \ / : : \ / : : \ / : : : : : : : :____________:______________: Any "ring neighborhood" in which the ring itself has an odd number of members cannot be tricolored. The reason is apparent: one color is reserved for the center, which borders on each other region. The other two colors have to alternate as one steps around the ring. But this can't be done if the ring is odd. The nontricolorable regions are easy to recognize (though for fleets, I was somewhat surprised at two of the answers!) once one understands this structure. We can identify them by their centers, and that's how I'll list them (thus, the region <vie, gal, bud, tri, ven, tyo> is singled out by its center, vie). For fleets: Adr; Iri; Bot. For armies: Vie; Ruh; Ukr; Bud; Boh. Are there any smaller nontricolorable neighborhoods? Well, if we allow "convoy neighbors" to be true neighbors which must be colored differently, then any set of four coastal provinces is nontricolorable! Otherwise, I believe 6 is the smallest size. A nontricolorable neighborhood of 4 would be easy to recognize, and there are none. It seems to me (though I haven't worked this out) that any nontricolorable neighborhood of 5 would include a nontricolorable neighborhood of 4! And, any nontricolorable neighborhood of 6 will be a ring neighborhood. So I think I've identified them all. Jamie The following two articles were scribed by dmb@sequoia.cray.com/David Bowen: Taken from Who Me? #19: A Defense of F Sev H by Robert Sergeant Mark Berch uses statistics to tell me how infrequent F Sev H is in the opening move and cites F Sev-Rum as a superior move, since it is used in 51.9% of the games. He tells us that Turkey will find it much easier to sell Russia on this opening than on F Sev H, which takes a lot of risks. Sure it does. I cite as the main advantage of F Sev H over F Sev-Bla that you immediately know whether you are allied with Turkey. Person- ally, unless I am holding the virgin sister of Turkey captive in my basement, I favor the bounce in the Black. It requires no trust in Spring 1901 between Russia and Turkey and if Turkey should stab in Fall 1901 you get the information before Turkey gets a center. The only reason for F Sev H is if you have decided on Turkey as your ally, but you know that Austria and Italy are allied. If that is your case, your Turkish ally will be in some trouble. He will have to use most of his strength in countering the attack and won't be able to help you much. In this case, F Sev H takes only the risk that your information about the joint Austro-Italian attack on Turkey is wrong. Even then, you can hope to talk Italy into a Russo-Italian alliance. But F Sev-Rum has one _big_ danger: the Fall move F Rum-Bul(ec) supported by Austrian army Serbia. Russia can either give to Austria to make up for the risk of Greece, or persuade Austria it is best to weaken the Turk. F Sev-Rum is the only move that can keep Turkey from getting a build in 1901. I'm not surprised that it is more popular. But if I were Turkey and Russia said he wanted to move F Sev-Rum, I would certainly go into the Black. That is the move to counter the loss of Bulgaria. And Turkey is supposed to _sell_ Russia on this move? Not likely. If Russia and Turkey are allied, I vastly recommend the bounce in the Black Sea. But if Turkey needs early development of his fleet, to my mind requesting F Sev H is the only strategy that makes sense. One thing about statistics for opening moves, they do not take into account the alliance structure. F Sev H is always (provided there isn't a nmr) intended as alliance with Turkey, but F Sev-Bla or F Sev-Rum does not reveal its alliance, so citing statistics in this case is really meaningless. It may be popular to move in a certain way, and it may be successful, but it doesn't say anything about what you are trying to do. Taken from Who Me? #19: On the drawbacks to F Sev-H: A reply to Bob Sergeant By Mark Berch In his article in _Why Me_ #16, Bob Sergeant discussed openings for the R-T alliance. One is the Black Sea standoff. For those cases where Turkey wants to develop the fleet more quickly, Bob states that "Russia does not want to put the fleet into Rum in the spring" but instead will want to do F Sev H. For strategic reasons I completely disagree. First, please note that F Sev H is a very rarely used opening. A British survey of 528 games (nmrs excluded) showed only 12 uses (2.2%). This isn't to say it doesn't happen---it was used against me (Aus) recently in 78HQ, but F Sev-Rum is vastly more common (51.9%). There is no good reason for this: if Turkey wishes to persuade Russia to avoid F Sev-Bla, it will be _easier_ to sell Russia, than F Sev H. Bob's tactical advantages of F Sev H are entirely correct. F Sev cannot be used against Aus, so a switch to an army will be needed. But F Sev H has several drawbacks for Russia, which in most cases more than balance its advantages. 1. Russia's failure to take Rum in S01 increases the chances that Austria can block its seizure in 1901 without Turkish help. If neither R nor A goes to Gal (eg A Mos-StP, A War-Ukr) and A has opened A Bud-Ser, A Vie-Bud, then A Ser S A Bud-Rum will block F Sev S A Ukr-Rum. Turkish support from A Bul can tip the balance. But T, figuring that will get Rum in '02 once he takes Gal, may wish to get a bit of a jump on his ally by trying to stand A out of Gre. This argument over the use of A Bul may sour the alliance before it is even firmly established. By contrast, A Ukr S F Rum locks up Rum without Turkish help. If Austria enters Gal in S01, the difference between F Sev H and F Sev-Rum is even more pronounced. With F Sev H, even with Turkish help, Russia must guess to gain a southern build. Without Turkish help, A Gal-War, A Ser-Rum assures Russia no build (this assumes A Mos-StP). 2. Russia's failure to take Rum in S01 can destabilize the R-T alliance. Suppose A and R have stood off in Gal. Many an Austria under those conditions will offer to support A Bul-Rum to gain an ally against the Russian enemy. Turkey may well find this offer attractive--after all, _Russia_ didn't offer him Rumania. Turkish ownership of Rum means that Turkey will have the upper hand in the A-T alliance, and will be relatively safe from an Austrian stab. This is an appealing prospect, and may look better to Turkey than a R-T alliance! Of course, A Ser S Tur A Bul-Rum won't take Rum against F Sev S A Ukr-Rum. But T may tell R:"I will do A Bul-Rum and decide my alliance structure in W01". Russia may well then decide that F Sev S A Ukr-Rum will not only not net Rum, but will irritate T as well. By contrast, A Ukr S A War-Gal will render Austria's support "irrelevant" (R may even chime in with F Sev S Tur A Bul-Rum), and his new army in Gal is in position to be an effective ally for T against A. The point here is that the Austrian offer of A Ser S T A Bul-Rum is attractive to Turkey because it presents a clear path to Rum if he can bully Russia. By contrast, if Russia does A Ukr S F Rum, A War- Gal in F01, A Ser S Tur A Bul-Rum is an impotent threat and thus T is likely to stick to his R-T alliance. 3. F Sev H reduces the Russian preparedness for a Turkish stab, and thus increases the likelihood of the stab. If T opens A Smy-Arm, F Ank-Bla, Russia's F Sev H will put her in a much worse position than F Sev-Rum, tho some guessing will be required in either case. Thus: a. If R can predict a supported attack on Sev (Turkey's most frequent continuation)(+ A Bul-Rum) A Ukr S F Rum-Sev holds Rum, defends Sev, _and_ leaves it open for a build. A Ukr S F Sev only defends Sev, nothing more. Further, unless R has A Gal, or unless A intervenes, T will take Rum in F01, stepping up the pressure on Sev in S02. b. If R can predict a supported attack on Rum (+ A Arm-Sev), A Ukr -Sev, A Gal S F Rum, and several other approaches can hold Sev and Rum and leave Sev open. But if he has done F Sev H, he can have Rum or Sev but not both, and Sev will likely not be open for a build. These examples all assume Austrian intervention. If he does, Russian expectations may change, but F Sev will normally leave him with less flexibility than F Sev-Rum. Yes, A could cut F Rum, but I am assuming A Bul-Rum, so it's cut anyway. Perhaps you are thinking: Yes, but this article is about a R-T alliance; if T opens with these moves there is no such alliance. However, if T sees that you are totally unprepared for the stab, that increases its attractiveness, and thus decreases the _relative_ attractiveness of the alliance. By agreeing to F Sev H, you are dangling a lot of temptation in front of Turkey. By the same token, suggesting A War-Gal, A Mos-Ukr, F Sev H to Russia, you as Turkey may well make Russia very suspicious. These are ideal moves for T to stab against: The fleet is in the wrong place and Austria antagonized with the move to Gal. Provoking such suspicion is a poor start for the T-R alliance. Arrayed against all these disadvantages is the tactical advantage Bob mentioned. It is not enough. Note that the switch can even be made in F01, _if_ things look favorable. A Ukr - Rum, F Rum - Sev/Bla, or in S02. Thus I disagree with Bob. If Russia decides against F Sev-Bla, he will want to do F Sev-Rum, not F Sev H. Turkey should have a tough time talking R into F Sev H, and in view of the suspicions that such an effort may engender in Russia, caution should be observed by Turkey in even _making_ the attempt. >*****************************************************************************< QUIZ <*****************************************************************************> From loeb@geocub.greco-prog.fr/Daniel Loeb: "How many different sets of opening orders are there? Such a set of orders must specify a legal movement, support, or hold for each of the 22 units on the board. (Convoys are of course impossible in Spring 1901.) You must consider all possible movements including stupid ones like moving Smy->Syr or Lon->Yor with Edi->Yor. However, you should only count supports which are NOT void. That is to say, the supported unit must be ordered to do what is supported to do. Furthermore, only count useful supports. That is to say, only count supports given by a country "A" for himself or a country "B" which in theory could prevent the success of the move or hold by a country "C" distinct from "A" and "B"." Here is a letter from chbrin5@dknkurz1.bitnet/Kai Hortmann: An algorithm to assign countries in Diplomacy ============================================= If you want to assign the 7 countries in Diplomacy to your 7 players, and you have a preference list from everybody, you can use the following algorithm: Count every player how gets his most prefered country as 1 Count every player how gets his second most prefered country as 4 Count every player how gets his third most prefered country as 9 Count every player how gets his fourth most prefered country as 16 Count every player how gets his fifth most prefered country as 25 Count every player how gets his sixth most prefered country as 36 Count every player how gets his least prefered country as 49 Add all the numbers and find the combination where this sum is lowest. If you look at the numbers above, you will note that its always the square of the players preference. So the combination with the lowest sum is the least square solution, something that is considered optimal in mathematics. As there are 7| or 5040 combinations, you can either use a computer or choose some of the most likely combinations and only calculate them. <* Kai Hortmann - chbrin5@dknkurz1.bitnet - Konstanz - Germany *> Taken from the October 19th Investor's Daily front page: AMID THE TAXFEST, SPENDING CUTS ARE RARE AND EVEN SOME MOVES ADVERTISED AS SAVINGS AREN'T MUCH MORE THAN FEE HIKES By Susan Mandel With all the concern over huge tax increases, much less attention has been paid to the spending side of the deficit-reduction package passed by Congress. Of the $500 billion in savings over five years that Congress has to come up with, $110 billion of it is supposed to come out of cuts in government programs. But not surprisingly, they have a funny way of doing that in Washington. "Not one bit of pork, waste, fraud and unnecessary spending will be cut of out of the budget", according to budget analyst Scott Hodge of the Heritage Foundation. In fact, government outlays would rise by 6% in 1991 under both the House and Senate budget proposals. The reason is that, aside from defense, the spending reductions are really cuts in the growth in federal spending. As Hodge notes, for every new dollar the government will get from higher taxes, it will spend $1.90. Even then, much of the so-called savings come from increases in government revenues. The House and Senate committees charged with the task of cutting federal program budgets were allowed to count the revenue from government fee increases as savings in spending -- an option they took full advantage of. "They're not decreasing spending. They're just increasing the fees and calling them "spending cuts", said Marc Wheat of Citizens for a Sound Economy. Congress didn't even bother mandating that the fee increases be used for deficit reduction. Of the $105 billion in spending reductions contained in the House version, at least $33 billion comes in the form of higher government fees. Nearly a third of those fee increases are accounted for by higher Medicare premiums and deductibles. The bill contains no actual program cuts. The only area that took a real cut is defense, which was dealt with in seperate legislation that would trim outlays by $182 billion over five years. "It's the usual tax-and-spead bill", said Larry Hunter of the U.S. Chamber of Commerce. "There's no domestic discretionary spending restraint. They're going to raise taxes, raise spending, and the deficit will continue to go up." Other than defense, the biggest cuts come out of the Medicare program. They are made, however, not by reducing benefits, but mainly by putting the squeeze on the doctors and hospitals that care for Medicare patients. The government would save an additional $33 billion that way. MEDICAID PROVISIONS The same applies to Medicaid. For example, the House bill requires drug companies to give state and federal Medicaid programs a 10% discount on prescription drugs. Congress expects the mandate will save the federal government $2.1 billion over five years and the states another $1.8 billion. Government farm subsidies take the next biggest hit, losing about $13 billion over five years. But that probably would have happened eventually anyway as a result of current General Agreement on Tariffs and Trade negotiations. The agriculture committees "are not giving up a lot", a Hill source explained. "They're seeing the handwriting on the all, and they're just enacting it into law." The next big-ticket spending reduction item is the suspension of lump-sum pension payments to federal retirees. Under current law, they have the option of taking their pension contributions out tax- free upon retirement and receiving a lower annuity in subsequent years. Suspending the lump-sum payments -- $30,000 on average -- for five years will save the government $7.6 billion. However, the policy change could prove to be more costly to the government in the long run, since it will have to pay retirees higher annuities in future years. Eliminating student loans for those in schools that have unusually high default rates -- mostly fly-by-night trade schools -- is expected to save another $1.7 billion over five years. And delaying student loans to first-year students by 30 days will net the government another $3.7 billion. The list of fee increases runs much longer. Banks will have to pay $9 billion more in federal deposit insurance premiums in the next five years, a strain that some people say is going to force some smaller operations out of business. Enforcement penalties under the Occupational Safety and Health Act and the Mining Safety and Health Act are expected to produce $1.3 billion in government revenues. The Nuclear Regulatory Commission will assess the nuclear industry for its cost of operation, bringing in $1.5 billion. The agency will also charge $25 million more for nuclear waste cleanup. The Environmental Protection Agency is going to charge carmakers $950 million for auto certification fees. The House bill also gives the Environmental Protection Agency general authority to charge another $168 million in fees for various services the agency performs. There is a $950 million increase in the tax on the tonnage of commercial vessels arriving from foreign ports. And the cost of mailing a first-class letter will go up by one cent, raising $5.8 billion to pay for Postal Service employee's health insurance and retirement benefits. Prescription co-payments for veterans raises $3.6 billion. And higher loan-origination fees on Veterans Administration loans raises $61 million. Finally, raising patent and trademark fees will net the government $495 million. This list of fees contained in the House-passed budgest reconciliation bill, similar to those in the Senate version, is incomplete, however. WILL CUTS MATERIALIZE? Economist Craig Roberts, former assistant Treasury secretary for economic policy under President Reagan, doesn't even believe the proposed budget cuts will ever materialize. According to him, they never do. Roberts pointed to the 1982 budget agreement, which raised taxes by $228 billion. There was supposed to be $3 in budget cuts for every $1 in increased taxes, he said. "This on paper solved the deficit problem forever", Roberts said. "(But) what happened? Instead of fixing the budget, spending went up to 158% of revenues and the deficit got worse." He noted that there has been a budget agreement almost every year for the past 10 years, each one with higher taxes. "If these budget agreements work", asked Roberts, "why haven't they worked by now?" Proposed '91 Spending Levels Program Area In fiscal '91 Change from '90 (billions) National defense $297.0 -1.0% International affairs 17.4 +12.3 Science, space, tech. 15.2 +7.0 Energy 4.0 +21.2 Natural resource, environ. 18.9 +6.2 Agriculture 14.1 +12.8 Commerce, housing credit 87.0 +15.0 Transportation 30.7 +4.1 Community, regional devel. 8.6 +3.6 Education 41.8 +9.1 Health 65.5 +12.5 Medicare 104.9 +8.3 Income security 160.5 +8.1 Social security 266.3 +7.1 Veterans benefits & svcs 31.7 +7.8 Administration of justice 12.3 +17.1 General government 11.7 +10.4 Source: House-Senate conference, Office of Management & Budget Below is an article by Michael Hall/hall@wildthing.bellcore.com and some discussion between him and Daniel Loeb/loeb@geocub.greco-prog.fr regarding the articles development. Thoughts on Programming a Diplomat By Michael R. Hall The Diplomacy Programming Project being orchestrated by Danny Loeb seeks to create automated diplomacy players, or "diplomats" (Diplomacy automata). It is difficult to give machines smarts, even in circumscribed domains such as Diplomacy. However, we need not throw up our hands in dismay; the fields of game theory and artificial intelligence (AI) have at least some of the answers. Nearly all AI and game-playing programs search. Search is merely the exploration of different alternatives. Humans search, but very slowly and with many mistakes. I am reminded of the EP game Tokugawa, when Danny Loeb as Austria and I as Turkey were at war, and I was surprised when Danny destroyed one of my armies - I had not foreseen the move, because I had not done a complete enough search of his possible moves. Computers, on the other hand, have the ability to search quickly and as completely as desired. There are two main search paradigms: breadth-first and depth-first. With breadth-first search, one examines all the nodes at the same level at the same time. Depth-first search involves going deep as quickly as possible. The following is an example tree. Breadth-first search would examine the nodes in this order: A, B, C, D, E, F, G, H, I, J. Depth-first search would examine them in this order: A, B, E, F, C, G, H, D, I, J. A /|\ / | \ / | \ / | \ / | \ B C D /| /\ |\ / | / \ | \ E F G H I J In a game, the nodes A through J would represent possible states. These states are reached by make moves (represented by the lines). For example, in the domain of tic-tac-toe, the states are the board positions, and the moves are to place an X or an O in an available location. The following shows how a complete search for X's move would go given a certain situation, with the colons (:) being used to denote empty spaces: :X: XOO current situation OX: /|\ / | \ / | \ X's turn (max) / | \ / | \ XX: :XX :X: XOO XOO XOO 1 ply look ahead OX: OX: OXX /| /\ |\ O's turn (min) / | / \ | \ XXO XX: OXX :XX OX: :XO XOO XOO XOO XOO XOO XOO 2 ply look ahead OX: OXO OX: OXO OXX OXX | | | | | | X's turn (max) | | | | | | XXO XXX OXX XXX OXX XXO XOO XOO XOO XOO XOO XOO 3 ply look ahead OXX OXO OXX OXO OXX OXX tie win tie win tie tie | final state evaluation Okay, we're searching, but what are we searching for? A state evaluation function is needed to evaluate the goodness of the effects of the moves. The value of the final state in tic-tac-toe is easy to analyze - if you have three in a row, you win; if your opponent has three in a row, you lose; otherwise, if all the spaces are filled, then it's a tie. These final state evaluations can be rolled back. Note above that two of the six possible final states (including the redundant ones) are winners for X. Then roll these evaluations back up the tree, assuming that O plays optimally and tries to minimize X's score. Once the evaluation is rolled all the way up to the top, X realizes that it will win, so long as he puts an X in the top left or top right corner and plays the next move correctly too - an X in the bottom right corner would cause a draw. Unfortunately, for nontrivial problems, it is impossible to search completely within a reasonable amount of time. Chess is an example of a game that cannot be solved completely within a reasonable amount of time, because each piece can move so many different ways and there are so many turns in a chess game. The combinatorial explosion that occurs during search is potentially deadly; even on the world's fastest hardware it would take longer than the history of the universe to "solve" chess. Because in Diplomacy the units move simultaneously, analyzing Diplomacy completely is even more hopeless! Imagine trying to evaluate all the possible opening moves for all the players simultaneously - since each unit has at least four possible orders, there's well over 4^(3*6+4)= 17,592,186,044,416 possible sets of orders for Spring 1901, so we can't even analyze the first turn completely, at least not within a reasonable amount of time on today's hardware. This means that we have two problems - 1) we must find ways to reduce the amount of searching - 2) we must find a state evaluation function that does not depend on searching until the end of the game. For the moment, let's assume we have a human available to evaluate the board states, and let's focus on search. There are a few things you can do to speed up search. First of all, obviously you should only look at your units and nearby units of other players. If you want to look at the whole board, then do it in pieces (divide and conquer). Second, you can also use a combination of breadth-first and depth-first search called best-first search. The idea of best-first search is that if you keep looking in what appears to be right direction at any given time, then you'll find the best set of orders more quickly. Generate all the valid orders for all the units. First, prune out any illegal or stupid orders. Next, evaluate the partial state generated by each of the orders *singly* - this is intended to be a quick check and probably won't involve looking at the opponent's orders. Assume any piece not (yet) ordered holds. Choose the order that seems to produce the best state, and fan out to the subsequent partial states. Then choose the partial state that seems best - this may be in a completely different part of the search tree than you were last working on. You might think that implementing best-first search would require storing the whole tree searched so far, but this is not the case. Only the current leading edge (i.e., the leaves) of the tree need to be stored in a list. This list is called an "agenda". More formally, best-first search may be implemented as follows: Initialize agenda to hold just the initial state node. Loop: Take the first node on the agenda. If the node is a goal node, then return it or store it and keep searching. If the agenda is empty, then stop. Get the successors of the node and evaluate them. Insert the successors into the agenda and keep agenda sorted. Continue looping. Of course, this best-first approach cannot be applied directly to analyzing the effects of the enemy's moves. You could take the paranoid conservative approach of evaluating a complete set of orders according to the worst state that can be obtained by some combination of enemy orders. Or you could assume that the enemy is attempting to maximize his own state given your orders, which does not necessarily undermine your state (since Diplomacy normally has more than two players, it is different from most games in this regard). You may wish to run seven processes in parallel (one for each country), which each try to devise orders against the best current orders of the others. If you can come up with a number of alternative sets of enemy orders, then you can evaluate a candidate set of orders according to how well it does on average given these various sets of enemy orders (this should result in a very robust set of orders that would work well in a wide variety of situations, but would also allow the diplomat to take some worthwhile risks.) Best-first search will not necessarily arrive at a solution quickly, so you may wish to modify it slightly to *first* do a form of depth-first search, choosing the best state at the current level to expand (but always moving deeper and never jumping to a different portion of the search tree.) Thus, it will rapidly find a set of not-too-stupid orders to turn in just in case the rest of the search bogs down and fails to complete within the available time. After this set of orders is found, it switches to the normal best-first search. One way to optimize best-first search is to have it prune redundant states from the search tree. In Diplomacy, this could be accomplished by sorting each set of examined orders in some way and then caching them. Any time that the diplomat started to evaluate a "new" set of orders, it would first check the cache to make sure that it is not simply a permutation of a set of orders that have already been evaluated. This will result in an exponential time savings with no loss of completeness, since whole redundant subtrees will get pruned. Another approach to speed up best-first search is to modify it to become a beam search, where a limit is put on the maximum number of nodes in the agenda at any one time. Of course when the beam limit is exceeded, it's the worst states that are discarded. My intuition is that looking ahead to future turns will often be futile, because the computer is likely to be wrong about the opponents' moves and the mistakes will get compounded for each turn looked ahead. However, it is certainly worth an attempt if the computer has identified two or more near optimal sets of orders and no other orders at the current turn seem worth exploring. Now, we still have to remove that human from the state evaluator. This will be hard, and I will present my thoughts on the state evaluator, but no doubt you may have some better ideas. I am assuming that the Diplomat has a module that knows the rules of Diplomacy well, if not perfectly. A state and a set of orders is passed into this module, and it produces a new state. Then this state must be evaluated. Suppose we're trying to develop a state evaluation function for Turkey. Now imagine a mountain with its peak in Turkey, sloping down to Greece, Austria, and Russia, and then down further to Italy and down further to France, Iberia, Germany and further down to England, and at the bottom is Scandinavia. The state evaluation at any given time could be the sum of the "altitudes" of the territories controlled by Turkey. This means that Turkey is very, very valuable to Turkey, which is what we'd hope. This does not mean that Turkey will leave all her units there, however, because she will still control the mountain peak even if she leaves it to take the lower ground (so long as no enemy sneaks through the front lines). Therefore, sets of orders that expand Turkey's influence to Greece, Austria, and Russia will be done generally before moving on to Italy and the rest of the world. Of course, if there's an opportunity to take, say, Naples, while Russia is putting up a tough fight around the Black Sea, then the state evaluation would be maximized by moving into Italy before Russia. There are a number of refinements we can make to this mountain model. First, territories with supply centers should be more valuable, especially in the fall, while territories that border many supply centers should be more valuable in the spring. (This was suggested by someone on rec.games.board a long time ago, when I threw up my hands at the problem of creating a diplomat.) Second, as Danny Loeb suggested, we might view the game at more abstract levels, with territories grouped together into provinces, and perhaps provinces grouped together into larger regions, and so on. Thus, if the system for some reason decided that it was important to go for Scandinavia, then it could raise the "altitude" of that whole region as well the territories leading up to it. A strategy of a diplomat might be to dominate one portion of this hierarchy before moving on to the next. This hierarchy could help in recognizing fronts and control, but it would be somewhat crude. Instead I propose a somewhat less crude measure. If a player has a unit in a territory, it controls that territory. Otherwise, if a territory is vacant, the nearest units share in the control of it. For example, if the closest units to Bulgaria are two spaces away, say, a Russian fleet in Sevastopol, a Turkish army in Budapest, and a Turkish fleet in the Ionian, then Turkey gets 2/3's of how much she values Bulgaria, while Russia gets 1/3 of how much she values Bulgaria. The theory behind this is that if there were suddenly a race for the territory, then all the units would get there at about the same time. Distance should take into account the accessibility of territories to armies/fleets; thus, for example, any army is infinitely distant from the Ionian Sea. This distance measure of control will cause the diplomat to desperately try to avoid letting "raiders" slip through its front lines. Unfortunately, it could make the Diplomat totally freak out and sound a retreat if a raider did slip through the lines, because the diplomat would think that it lost practically all the (presumably valuable) territory behind the lines, whereas a single unit could only steal a single supply center per year. This problem could be reduced by dividing the influence of a unit by the number of territories it has a share in controlling, and also letting a player's owned home supply centers exert control, since units could be built there (but probably the distance should be a little greater, since the units don't yet exist and might never.) Also, any owned supply center or occupied unowned supply center should give a bonus to the owning player's state evaluation, regardless of the status of "control". A further refinement would be to have units exert partial control in any adjacent territories, even those occupied by enemy units. Now comes the aspect of state evaluation that I've agonized the most over. An example will illustrate the problem best. Suppose Turkey has taken over half the board and builds an army in Smyrna. The question I pondered was "How do we make the state evaluation encourage the movement of the army towards the `front'?" My above notions of "control" would not make the army move towards the front. I finally decided I was not asking the right question. Although most of the smarts should be put into the state evaluator, some smarts can be put into the order generation and agenda sorting. For example, a heuristic like "always prefer a support order in preference to a hold order" can more easily be put into the agenda sorting (or move generation) routine than the state evaluation routine (which is supposed to be "static" and just look at the resulting board state, not the orders themselves per se.) So, we can add a heuristic to make it prefer orders that move in the "right direction" over all other orders, everything else being equal (i.e., the state evaluation being the same.) The hierarchy of territories can be used to give a notion of the "right direction". An alternative is to adopt a gravitational attraction analogy, where the unit would be seek to reduce the distance between itself and uncontrolled (or partially controlled) territories, weighting valuable territories proportionally more and distant territories much less. The idea is to have the unit prefer to move to where it can do the most good in the least time. For example, this will insure that Turkey does not open with A Smy-Syr, because that would move it away from valuable partially controlled territories; even if its state evaluation were the same as the other orders, the best-first search would put A Smy-Syr "behind" the other orders. This preference to move towards the front *could* be incorporated directly into the state evaluation, but then it has to be set up carefully to always be a less important factor than control. You will probably want to store "book openings" to give your program a little head start, but let's walk through how Turkey might generate its opening moves. First, the diplomat adjusts the values of holding certain territories according to its current foreign policy, the season, and so on. Let's suppose that the territories have these values: Con=100, Ank=90, Smy=90, Syr=50, Arm=60, Bla=60, Sev=70, Rum=50, Bul=70, Gre=60, Aeg=60, EMe=50, Ion=50. Next the diplomat begins the best-first phase. Initially, we start with a list with one element, the null order set: ({}=815) In the above notation, the outer parentheses mark the beginning and end of the agenda, the braces surround the current order set, and the number after the equal sign is the evaluation of the state achieved by this order set. The null order set is equivalent to "all hold". The state evaluation of "815" was obtained by summing up the values of the territories occupied by Turkey plus a proportion of the values of territories that a partially controlled. (For example, it gets 40 points for Arm, 2/3's of its total worth of 60, because two of Turkey's units could move there in one turn, while only one of Russia's could move there in one turn.) I am assuming a 100 point bonus for owned supply centers and a 50 point bonus for opponent/neutral supply centers that are occupied in the spring. Next, this element is removed from the agenda, and all the legal first moves from one unit are generated, the resulting states are evaluated, and the order sets are sorted: ({A Con-Bul}=959, {F Ank-Bla}=870, {A Smy-Arm}=845, {F Ank-Arm}=845, {A Con-Smy}=815, {F Ank-Con}=815, {A Con-Ank}=815, {F Ank-Con}=815, {A Smy-Con}=815, {A Smy-Ank}=815, {F Arm SA Con}=815, {F Arm SA Con}=815, {A Con SF Ank}=815, {A Con SA Smy}=815, {A Smy SA Con}=815, {A Smy SF Ank}=815, {A Smy-Syr}=815, {A Con H, F Ank H, A Smy H}=815) There's no need to generate support orders for moves before other units have moved. Also, there's no need to generate hold moves explicitly in the search, since units are always assumed to hold if they do nothing else, and holding will not change the state evaluation. (Fine point: Notice the "all hold" element second from the end. It inserts this near-equivalent of {}=815, just in case holding is actually the best thing to do. If this were to ever get to the top of the agenda, it would test holding all its units against enemy orders.) Each of the possible moves is tried individually and the resulting partial states are evaluated. A Con-Bul is extremely valuable, giving Turkey new influence in valuable areas as well as occupying a neutral supply center. F Ank-Bla is good since it gives Turkey influence in Rumania, but it's not as good as A Con-Bul, especially since it doesn't grab a supply center. (Remember, the computer doesn't do all these rationalizations, at least not at this time - it just looks to maximize the evaluation function.) So, A Con-Bul is made as the first step in the search and this order set is removed from the agenda. Next, all the legal second moves given A Con-Bul are generated and inserted into the agenda (asterisks mark the new elements): (*{A Con-Bul,F Ank-Bla}=1014, *{A Con-Bul,F Ank-Con}=1004, *{A Con-Bul,A Smy-Arm}=979, *{A Con-Bul,A Smy-Ank}=959, *{A Con-Bul,A Smy SF Ank}=959, *{A Con-Bul,A Smy-Syr}=959, *{A Con-Bul,F Ank H, A Smy H}=959, *{A Con-Bul,F Ank-Arm}=949, *{A Con-Bul,F Smy-Con}=939, {F Ank-Bla}=870, {A Smy-Arm}=845, {F Ank-Arm}=845, {A Con-Smy}=815, {F Ank-Con}=815, {A Con-Ank}=815, {F Ank-Con}=815, {A Smy-Con}=815, {A Smy-Ank}=815, {F Arm SA Con}=815, {F Arm SA Con}=815, {A Con SF Ank}=815, {A Con SA Smy}=815, {A Smy SA Con}=815, {A Smy SF Ank}=815, {A Smy-Syr}=815, *{A Con H, F Ank H, A Smy H}=815) Here the moves that increase the state evaluation the most are F Ank-Con and F Ank-Bla, since these are at the top of the list. The state with F Ank-Bla is explored first, since it seems slightly better. The allowable subsequent orders are: F Smy-Con, A Smy-Ank, A Smy-Syr, A Smy-Arm This yields the following (again, asterisks mark the new elements): (*{A Con-Bul,F Ank-Bla,A Smy-Arm}=1034, *{A Con-Bul,F Ank-Bla,A Smy H}=1014 *{A Con-Bul,F Ank-Bla,A Smy-Syr}=1014, {A Con-Bul,F Ank-Con}=1004, *{A Con-Bul,F Ank-Bla,A Smy-Con}=1004, *{A Con-Bul,F Ank-Bla,A Smy-Ank}=989 {A Con-Bul,A Smy-Arm}=979, {A Con-Bul,A Smy-Ank}=959, {A Con-Bul,A Smy SF Ank}=959, {A Con-Bul,A Smy-Syr}=959, {A Con-Bul,F Ank H, A Smy H}=959, {A Con-Bul,F Ank-Arm}=949, {A Con-Bul,F Smy-Con}=939, {F Ank-Bla}=870, {A Smy-Arm}=845, {F Ank-Arm}=845, {A Con-Smy}=815, {F Ank-Con}=815, {A Con-Ank}=815, {F Ank-Con}=815, {A Smy-Con}=815, {A Smy-Ank}=815, {F Arm SA Con}=815, {F Arm SA Con}=815, {A Con SF Ank}=815, {A Con SA Smy}=815, {A Smy SA Con}=815, {A Smy SF Ank}=815, {A Smy-Syr}=815, {A Con H, F Ank H, A Smy H}=815) [continued in issue #212] Publisher comments: Quote was provided by ingram@u.washington.edu/Doug Ingram ****************************************************************************** To join in the fun, send your name, home address, home and work phone numbers, and country preferences to Eric_S_Klien@cup.portal.com. ****************************************************************************** Up