Puzzle Number 14: Fair Game?

We have just started looking in detail at randomized algorithms in my computational complexity course. In addition to being a fascinating topic, it is also full of all sorts of fantastic results that make for great puzzles.

This puzzle takes the form of a game for two players, Player A and Player B. Player A has two cards, and he must write a distinct non-negative integer on each card, then lie that card face down on the table. Player B then chooses to flip over the card either on the right or the left, view the value of the number recorded, and must guess whether that value is greater than or less than the number on the other card. Player A is sneaky, however, and adds a rule that Player B must tell Player A the method he will use for determining his guess before they play the game (and Player B is not allowed to deviate from it).

Even with Player A trying to obtain an unfair advantage, it is relatively straightforward to show that Player B can still come up with an algorithm to make his guess that will make the game a fair one (each player has an identical chance of winning):

Player B's Fair Strategy:

Flip over the left card.
If that card has the value 0, guess that the other card's value is larger;
Else randomly (with a 50% chance either way) guess that the other card's value is larger or smaller.

Knowing this strategy ahead of time, Player A will obviously never put a zero on the left-hand card. Other than that, however, there is nothing he can do to increase his odds of winning above 50%, and the game is therefore fair.

Is this the best that Player B can do, or is there an alternative algorithm that he can use that will put his chances of winning above 50%? If there is, what is that algorithm?

Game Review: Diplomacy, Part III: End Game Analysis

After many months, I figure it is time I finished my rudimentary analysis of the game Diplomacy. For reference, here are links to Part I (game description) and Part II (opening and mid-game analysis).

To briefly recap, the second stage of the game occurs when all (or at least most) of the neutral supply centres have been occupied by one of the seven major powers. Most players are on nearly equal footing in terms of military size, and the number of players means cooperation with at least one or two others is necessary to overcome an opponent (even though the game is zero-sum in terms of any progress made by one player is at the expense of another). The third and final stage of the game is difficult to concretely separate from the second, but it basically happens when some players begin to lose badly and others expand their military to impressive sizes of ten or more units. At this point one or two players may even be eliminated from the game. While in my experience this seems to happen most often to either Germany or Austria-Hungary (being in the centre is an unfortunate place to be), it doesn't always. Russia makes a large and tempting target, and a Russian leader lacking vigilance might find himself victim of a disastrous invasion from the north through Scandinavia, Finland, and the Barents Sea, or from the south (especially if the Turks manage to get a fleet in the Black Sea). Even Great Britain, which is notoriously difficult to invade (but, at the same time, notoriously difficult to expand from) can be defeated, especially if France and Germany team up and devote some resources to developing their fleets. If enemy ships manage to enter the English Channel and the North Sea, the British are in a lot of trouble.

Regardless of who has found their fortunes dwindling and their dreams of European dominance shattered, as the dust settles the remaining juggernauts begin to face the same predicament that spurred the first round of wars: to expand their empires, they need a target to conquer. The difference at this point, however, is that interactions between players are now often more complicated. Many turns have gone by in an alliance against a foe, but with that foe gone, players begin to wonder how long the alliance will continue. Additionally, those doing exceptionally well at this point begin to grow cocky; victory is looking more assured, as their militaries are now three to four times as powerful as they originally began. It is hard to give much analysis for this part of the game, since the situation is virtually impossible to predict. This is also the part of the game that I have the hardest time with, simply because I don't like the concept of backstabbing an ally. While it very often is advantageous to strike without warning (especially if you and your ally are doing equivalently well or he is even doing better), I have a hard time emotionally with that. It might sound like I am making myself out to be a nice guy here, but I'm not entirely sure that is the case, either. It could be a remnant of chivalry that makes me feel this way, but it could also be a testosterone driven alpha-male style arrogance in which I want my foe to know that I'm coming for him and still have no way of stopping me. I like to think it's the chivalry side of things, but who knows.

Anyway, I am wandering away from the topic at hand. Often people actually don't make it this far in Diplomacy (it is an awfully long game for a single sitting), and simply stop after a player or two is eliminated (or even before if time players need to leave) and simply count up the number of supply centres under each person's control, determining rank in that manner. I hope in my ruminations on the subject I have done Diplomacy justice, and perhaps I may also manage to convince some of my readers who actually know me and have always begged off playing to give it a shot.

Game Review: Diplomacy, Part II: Opening and Mid-Game Analysis

A little while ago I devoted some time to describing the game Diplomacy. Here is the first continuation of that post, devoted to analysing what I find interesting about the game.

Note: A map of the board can be found here. When I mention specific territories, most of them have obvious three letter abbreviations (usually the first three letters of the territory's name), but if there is any confusion, the list of standard abbreviations can be found here.

The game has roughly three stages. The beginning of the game is characterized by many neutral supply centres available around the map for enterprising European powers to take over. For example, France pretty much immediately annexes the Iberian peninsula, netting the valuable pair of supply centres in Spain and Portugal. Italy picks up Tunis, Austria-Hungary envelopes Serbia, Turkey buffers their border with Bulgaria, Britain moves onto the continent by occupying Norway, and Germany grabs Denmark. Of course, this might not happen, but all of those captures are possible to perform without any interference from another player (as long as it is accomplished within the first year (two turns)). The only country that is not guaranteed to take control of a supply centre in their first year is Russia, and that is only if Germany decides to be a jerk and, in the first turn, moves the fleet in Kiel to Denmark then follows up the next turn by attempting to move that fleet to Sweden, likely blocking the fleet sailing out of St. Petersburg either through the Gulf of Bothnia or along the coast of Finland.

Similar to Sweden, there are a large number of more contentious supply centres scattered about the map. Romania is easily contested the first turn between the Austrian-Hungarians and the Russians (as long as the Russians are willing to not attempt moving their fleet into the Black Sea and risk the Turks occupying that vitally strategic body of water). Similarly, Greece is not immediately available to any power, but within two turns could be occupied by either the Italians, Austrian-Hungarians, or Turks. The Austrian-Hungarians and Italians are likely to already be wary of each other due to the border between Trieste and Venice, the only pair of starting supply centres that border each other. Like the triple entente created over the question of occupying Greece, the British, French, and Germans face a similar conundrum over the occupation of Belgium.

Anyway, so the first few turns consist mostly of people being self-absorbed with their own easy expansion. Initial rounds of diplomacy tend to be fairly sparse and open (at least with beginners to the game. Some veterans or avid fans of Machiavelli might leap headfirst into shadow and intrigue). At this point the game is not excessively interesting, as it is essentially a non-zero sum game where everyone wins. However, the degree to which one 'wins' (i.e. expands the size of one's military) can have massive ramifications on the following stages of the game.

The second stage of the game occurs within a few turns, and it happens when virtually all supply centres are occupied by one of the major powers. Here is where tensions begin to build. Essentially, all players are likely to be fairly evenly pitted with between four and six units under their control (seven or eight if they have done well, an opponent made some early blunders and failed to grab open supply centres, or they have already declared open war and are making remarkable progress). At this point the only way to increase one's position is at the expense of someone else. However, while in that sense it is a zero-sum game, the number of players makes cooperation (at least to a certain degree and with certain favoured allies) still the most effective strategy. This is when the game becomes psychologically interesting, as groups and pacts begin to form. Some alliances are forged out of fear (either of each other or a third party), and it is fear that makes doing excessively well in the opening rounds sometimes less desirable. For example, if France grabs the Iberian Peninsula (gaining two supply centres) as well as Belgium and Holland (giving a grand total of seven supply centres counting their starting territories of Paris, Brest, and Marseilles), the intimidating sea of light blue units might be enough to galvanize a disastrous alliance of Britain, Germany, and Italy. This is especially true since having a large number of units not only makes one powerful, and therefore fear inspiring, but it also makes one an attractive conquest since it leaves many supply centres to be neatly divided amongst the conquering parties. That said, in the situation just outlined an enterprising leader of France might manage to convince the Russians or Austrians to come to his aid with a promise of mutually beneficial spheres of influence divided between the two of them, thus forcing his German or Italian opponents to fight on two fronts. Other than fear as a motivating factor, one also needs to contend with greed and an odd sense of temporary goodwill (of course, an exhaustive list is unlikely to be generated, since one can always come up with a fairly unique motivational mindset, but I think the biggest two are fear and greed. Perhaps I only think that, though, because I've been reading Machiavelli lately).

Of course, I am once again getting caught up in details when I intended to give an overview. Beyond the psychological interest of the second stage of the game there is also an interesting mechanical aspect to it as the players learn how best to maneuver their troops and vie for strategic territories. While the Black Sea is of immediate strategic importance for the Turks and Russians from the very beginning and the border between Trieste and Venice sparks immediate tensions for the Austrian-Hugarians and Italians, several other territories that are not supply centres take on an increasingly important role in any but the most trusting of relationships (or relationships characterized by completely ignoring each other due to focusing on another front): the English Channel between England and France, Burgundy between France and Germany, Piedmont between France and Italy, Bohemia between Germany and Austria-Hungary, Galacia between Russia and Austria-Hungary, and the whole mess that is the Balkans between, mainly, Austria-Hungary and Turkey but also of significant importance to Italy and Russia. Of course, there are other territories that can also become quite significant. The North Sea is vital for anyone trying to attack Britain from the east, Scandinavia can become quite hotly contested between Britain, Germany, and Russia, and sometimes something completely unpredictable happens (such as one game I played in which Russia sailed a lone fleet all the way around the edge of the map and happened to snag Portugal from the French).

For the final stage of the game and some more fancifully meandering analysis, stay tuned for part III.