Author Archives: Fishbreath

Thirty Minutes Over Toseong

Posted by

Come, let us reminisce.

It’s the mid-2000s, and war has broken out over the Korean Peninsula. I climb into my F-16C Block 52, get her powered up, and listen to the radio chatter as the inertial navigation system aligns. The time is just after noon, and the tower welcomes a few flights back. Good. The war only started this morning, but losses of planes and pilots both have been heavy.

The INS is aligned, and the Data Entry Display, the little green screen beneath and to the right of my HUD, informs me that my takeoff time is in five minutes. I radio the tower, and they clear me to taxi to runway 20R at our airbase, Seosan, a little ways southwest of Seoul. In between lining up another flight for landing on runway 20L, the tower gives my little two-ship clearance for takeoff.

We’re loaded light today, four AMRAAMs and two Sidewinders, so I take off at military power to save on fuel. We turn east-northeast and climb. We’re to our rendezvous point in about ten minutes. A few miles behind us, the ground-attack flight we’re escorting slots in. I check in with Chalice 4, the AWACS flight covering our sector of the front, and he advises me of bandits to my west, heading this way. I dither for a moment: should I push west and deal with the bad guys, or stick close to my flock?

On the assumption that close escort is and always has been dumb, I turn west. I match the bullseye position on my radar MFD page to the position AWACS gave me, and sure enough, I see two contacts headed my way. I hand one off to my wingman, bug the other, get target confirmation from AWACS, and send the first AMRAAM on its way. It hits, and my wingman’s does too. AWACS calls picture clear, and I turn my flight back toward our charges.

Of course, this is a full-scale war. There’s no way our sector will keep quiet for a full half-hour. Sure enough, AWACS reports contacts about 60 nautical miles distant, inbound from the north. We have identifications: one or two MiG-23s in the middle of a big group of Il-28s. Neither are particularly fearsome, but the MiGs should go first on principle—the Ilyushins are ancient jet bombers, dating from the late 1940s or 1950s, while the MiGs have some 1970s-vintage missiles that might pose a threat to us if they get close enough.

This is where things start to get a little hairy.

It isn’t that engaging the MiGs and Ilyushins doesn’t work—it works just great. The problem is that we still have ten minutes left on station. AWACS calls out a close threat—so close they give us a bearing and range, instead of a bullseye call—and my wingman goes low to deal with the MiG-19 that apparently managed to get in underneath us. Having pushed a little further north than I wanted while prosecuting the bombers, I turn south to extend, and take stock of my situation. I’ve fired all four of my AMRAAMs, and I have a pair of Sidewinders left on the rails. My wingman splashes the MiG-19 down low, and I call him for his status. “Winchester,” he says, “fuel state 2000.”

Well, that’s no good. He’s out of everything and has enough fuel to make it back to Seosan. I send him home, and call AWACS to let them know I’m effectively empty.

“Lobo 9-1, Chalice 4, your window of vulnerability is still open. Can you hold out?”

Well, crap. “Wilco,” I reply, on the assumption that an F-16 with no long-range missiles at angels 25 looks, on radar, to be very similar to an F-16 with long-range missiles at angels 25.

Then the RWR chirps in a way I’m too familiar with. The new threat is a MiG-29. I call AWACS again. “Nearest contact bullseye 050, 60 nautical miles.” I fiddle with the horizontal situation display MFD page, and verify that those are indeed the Fulcrums, sixty or seventy miles out. I ask if I can go home again, and they insist I try to hold out a little longer. There isn’t really much holding out to be done, though. I can’t take on a pair of Fulcrums on my own.

I can stick around a little longer, pretending to be armed, though. I have one eye on the clock, one eye on my RWR, and both ears listening to AWACS updates. It’s agonizing—the MiGs are closer to a missile shot every minute, and I don’t have the fuel to run away at afterburner for very long. Finally, the clock ticks past the edge of my station time. I call AWACS and tell them I’m out of Dodge, and I put the MiGs on my six and run for home.

So ends this tale of a rarity in gaming: a moment when I was not only happy to escape, but actually planning on running away.

The games I’ve enjoyed the most over the years have a common theme: they make war stories. Whether it’s the one time in PlanetSide where I used a Galaxy to scrape the enemy off of a hilltop position, or that time I was stuck on-station with MiGs bearing down on me, it’s the sort of immersion that resonates with me the best. That’s the best thing I can say in favor of Falcon 4 BMS.

Skypirates: a zeppelin aircraft carrier construction ruleset

Posted by

Every zeppelin which has played a major role in Skypirates to date (so far, only Inconstant and Arys, where parvusimperator’s characters are based) has been designed in accordance with a fixed set of rules. We appreciate the verisimilitude this lends proceedings, for one; for another, we just really like rules for designing things. Ask parvusimperator about tanks or IFVs sometime1.

But not now. We have zeppelin rules to cover. I believe parvusimperator, to whom I owe the credit for these, believes he originally stole them from some Germans2, which is apropos. They were designed for tabletop RPG rules system Savage Worlds, which I wholeheartedly recommend if you’re looking for something opposite GURPS on the fun-GURPS axis. In traditional RPG fashion, round in the least favorable manner unless otherwise stated.

These are primarily construction rules. They were borrowed for a Savage Worlds campaign that never happened, and so the portions of the rules pertaining to acquisition and combat were never really fleshed out. If you want to use them, you’ll have to do some innovation. (If you do, let us know! We’ll put them up here for the benefit of posterity.)

Hulls

Length(m)    Width(m)    Hexes     Lifting/Payload (t)
300                50      6x1                 425/275
350                60      7x1                 670/435
400                65    8x1.5                1000/650
450                75    9x1.5                1425/925

The listed payload assumes helium as a lifting gas, military-spec internals (protected against enemy fire), and a single keel, and is 65% of the lifting capacity, rounded to the nearest 5t. For hydrogen lifting gas, add 5%. For civilian-spec internals (not protected against enemy fire), add 5%. For triple keels in the style of USS Akron and USS Macon, which permit internal engine mountings, subtract 5%. (That is to say, the maximum payload achievable is 75%, using hydrogen lifting gas and civilian internals, and the most durable build achievable is helium, milspec, and a triple keel.)

Take the product expressed in the Hexes column, and write it down as your hex-volume.

Engines
1 ton & 1 crew (slow diesel engine),
3 tons & 1 crew (normal diesel engine),
5 tons & 2 crew (fast diesel engine)

One engine pod is needed per every hex a zeppelin is long, rounded down to the nearest even number.

Gun Turrets
1/2 ton & 2 crew for cal. 30 MG
1 ton & 2 crew for cal. 40 and 50 MG
2 tons & 2 crew for cal. 60 and 70 MG
2 tons & 1 crew for flak cannon

Machine guns may be single or double turrets. Their requirements are the same, excepting acquisition costs. Turreted flak emplacements may only hold a single gun. Add a +3 modifier to shock rolls for the gunshield.

Bow/Stern Turrets
2 tons & 2 crew for cal. 60 and 70 MG
2 tons & 1 crew for flak cannon

The bow/stern mounts can hold one gun mount or one rocket mount or one aerial minelayer. Only one thing.

Broadside Guns
2 tons & 2 crew per gun

Each gun deck may mount up to six guns per side, and are retractable. Five rounds are stored at the mount; more are brought up from the holds. Broadside guns may be directed from the bridge for firing at zeppelins or ground targets within the guns’ effective range. The gun crews may fire under local control when attacking aircraft.

Broadside guns are typically flak guns, in similar calibers: usually between three and five inches (76 to 127 mm).

Bomb Rack
5 tons & 1 crew

Some military zeppelins mount bomb racks on the underside of the hull. It mounts eight hardpoints’ worth of bombs. It may not be used to fire rockets. Bombs must be accounted for in cargo. Bombs are released from the bridge.

Rocket Rack
10 tons & 2 crew

Rocket racks provide eight hardpoints for aerial rockets. Bombs may not be dropped from rocket racks. Rocket racks may be placed at the bow or stern, or to replace broadside guns. Ammunition must be accounted for in cargo. They are fired under local control.

Control Room
[Length of hexes of the zeppelin / 2] tons and [Length of hexes of the zeppelin] crew
The bridge includes a chart room and a radio room. Sometimes, military zeppelins place these rooms separately. Civilian zeppelins always place them in the control gondola.

Cabins
1 ton & 1/4 crew

Crew are required only for passenger cabins. Accommodations aboard a military zep do not require crew.

For your one ton, you may have any one of the following: one luxury cabin (for one person, a first-class passenger or senior officer), one suite (each person requires one ton of accommodation; a suite for five people weighs five tons), one double cabin (aboard a passenger zeppelin, tourist class), one quadruple cabin (economy class), or one cell for up to eight prisoners.

Crew Rooms
2 tons & 1 crew

For your two tons and one crew, you may have any one of the following: one extra chart room, one extra radio room, one kitchen section (one section required for every ten cabins), one dining room section (one section required for every ten cabins), one lounge (suitable for ten tourist or economy class passengers, or two first-class passengers), a library (which may be expanded), an arboretum (which may be expanded), an observation deck, a briefing room or flight command center, or a science laboratory (which may be expanded).

Aircraft
We have a set of aircraft design rules which are not reproduced here. It suffices to say, for the remainder of this post, that zeppelin-borne aircraft come in airframe sizes ranging between 4t and 15t, and their weight in tons is their size for the purposes of these rules.

Internal Skyhooks
[3*size] tons & 5 crew

A traditional docking hook used to launch and recover planes: the skyhook drops planes out the bottom of the zeppelin, and extends into the air below the bottom of the zeppelin to recover them. Each skyhook may launch or recover one plane per round. The size specifies the largest plane that may be launched or recovered.

External Skyhooks
[2*size] tons & 1 crew

Skyhooks mounted outside the zeppelin’s hull, frequently used for emergency exits or as emergency landing spaces. Each may hold one plane, its maximum size specified by the skyhook’s size. The pilot gains entry to the zeppelin by means of a small ladder. Moving large cargo between an external skyhook and the zeppelin’s interior is impossible.

Launch Bay
[5*size] tons & 15 crew

Launch bays are used in the largest military zeppelins. Each may launch two planes per round, but may not be used to recover aircraft. The size specifies the largest plane that may be launched.

External Refueling Rig
[2.5*size] tons & 3 crew

Refueling rigs are external skyhooks with plumbing to refuel docked planes. Each plane may be refueled in one round. (It therefore takes a three-round cycle: recover in round one, refuel in round two, launch in round three.) Otherwise, they function as external skyhooks.

Hangar
[ size of air wing ] tons & 1 crew/10 tons

The size of the air wing refers to the sum of its weights. The hangar is an internal space in the zeppelin with room for parking, access to the launching systems, and facilities for refueling and rearming planes, as well as stowage for aircraft stores. Any zeppelin with a launch bay or an internal skyhook must have a hangar.

Repair Bay
[2*size] tons & 5 crew

Repair bays contain tools and equipment for disassembling, maintaining, and repairing planes. A hangar and an internal skyhook are prerequisites. The size specifies the largest plane which may be serviced.

Provisions
1/2 ton food/water/etc. per person per month.
1 ton per plane per combat sortie. (Includes fuel and ammunition, as required.)
1/2 ton per plane per non-combat sortie. (Includes fuel only.)
1 ton of ammunition per zeppelin gun of any type.

Engine Speed

Engine          Fuel/day (tons)  Speed (hexes)   Speed (mph full/economy)
Diesel, slow      Volumehex / 5              1                     50/10
Diesel, normal    Volumehex / 2              2                     65/15
Diesel, fast          Volumehex              3                     80/20

For travel, engines can be run at full speed, consuming the listed amount of fuel per day. They may also be run at economy speed, using the second number in the speed column and consuming half the listed amount of fuel per day.

Fuels
Engines may be fueled by blaugas, gasoline, or diesel, which are identical for our purposes. (Zeppelins which run gasoline engines may share fuel with the air wing.)

Cargo Hold
[any size] + 2 tons

The two tons are for handling equipment, and do not count toward capacity.

External Cargo Platform
[any size] + 2 tons

Smaller freight zeppelins sometimes use an external platform mounted under the hull. These are much cheaper for a given capacity, and may also be used as an emergency hangar for small planes. The cargo capacity is 1.5 * size. The two tons are for handling equipment, and do not count toward capacity.

Cargo Winch
[2 tons + cargo weight] & 2 crew

A cargo winch lowers a section of the cargo hold floor beneath the zeppelin, which may be used to easily load cargo without the use of ramps or slings.

With modifications, the platform may be used as an emergency landing point. Add one ton to the mechanism. The winch’s rated capacity must be twice the size of the plane. A plane making an emergency landing on a cargo platform loses its engines.

Zeppelin Harpoons
[5 + length in hexes of largest zeppelin which can be towed] tons & 4 crew

Intended to tow disabled zeppelins for repair, pirates sometimes modify the towing mechanisms to serve as grappling harpoons.

1. Or just read his posts here.
2. As he said, “IIRC, ja.”

The Crossbox Podcast

Posted by

So called because parvusimperator wanted a Clarkson-esque name like ‘Crossfire’, and I was thinking something utilizing the current branding, like ‘Soapbox’. You get the middle of the road solution nobody wants1.

Today’s show features: the US Navy’s Bad Idea™, surprisingly similar handgun choices, and wargames that get us good.


(Download)

1. I guess it sounds kind of like the box in which you might cross-examine someone, which does capture the usually-adversarial nature of our little chats.

On tafl: game tree search optimizations

Posted by

As you’ll recall from the tafl piece about complexity, tafl has a high branching factor compared to, say, chess1. That means that a tafl game tree is broad: it has a lot of nodes relative to its depth. Since searching deep into a broad tree is difficult, getting good lookahead out of a tafl engine is going to be difficult. And, to be clear on where this post is going, it started off being extremely difficult.

Before I get there, though, I want to talk about the state of the art in chess AI as of now, or at least a few years ago. (Recent sources are probably easy to find if I were to look in the right places, but I forgot I still have a .edu email address with which I can probably sneak into a bunch of online article repositories.) Chess engines, today, on a moderately powerful desktop computer, are able to generate about four million game states per second. They also have highly advanced pruning2: not only the standard sort I’ll go into in a later post, but also a more qualitative sort, discarding moves that pass the plausibility test but fail the usefulness test.

Four million states per second is an extremely high bar to hit. Chess engines have been in development since the dawn of digital computing, just about, and fifty to sixty years of optimization really shows3. I told myself I’d be happy with somewhere between ten and twenty-five percent of chess’s state of the art.

How far did I have to go? Well, I coded up my state explorer, put a bit of benchmarking code in, and set it exploring three ply deep in brandub. It chugged along for a while, and then, almost forty seconds later, finished. The number? 1,000 states per second, which comes to between four hundred and one thousand times too slow.

Ouch.

I quickly discovered a few obvious things I could fix. First, I was doing an expensive operation (getting the allowable moves for a piece) for every piece on each side, to check if either side had no allowable moves remaining. I replaced that with a short-circuit check that returns true as soon as it discovers any allowable move for either side, which is a much quicker proposition. Second, I was checking for edge forts at the end of every turn, whether or not the game allowed for edge forts. I put a stop to that. Third, I was checking for edge forts in a vastly more expensive way than I needed to, to allow for a situation that does not occur in any known tafl variant4.

Confidently, I ran the benchmark again: 4,000 states per second.

Well, I’d been hoping for more than that.

I did a little reading, and decided some of my problem was with the programming language I’d selected. My language of choice for most of my side projects is a scripting language called Groovy. It’s Java’s little brother, sort of; it provides a bunch of shortcuts Java does not for displaying things to the terminal, handling user inputs, playing around with files, and iterating over sets of objects. I suspected from the start that Groovy might cause me headaches, and profiling suggested that was correct—my code was spending most of its execution time in Groovy’s internals. Rewriting it in Java was quick, as such things go, and with that squared away, and me optimistic as to my chances, I set up another benchmark.

15,000 states per second.

Three times faster is great, but I still had a few orders of magnitude to go.

I decided that the board representation I had started with was clever, but inefficient. My profiler suggested I was using literally tens of millions of objects: each space was a first-class object, in the first reckoning. This would not do; objects in Java may be small, and instantiating them may be fast, but there’s a limit to what a Java virtual machine can be expected to put up with. I removed the class of object which represented spaces, and set about rewriting the code to reference an array of small integers to represent a board.

Moving to an integer representation meant that I had an opportunity to come up with an encoding I can eventually use to rid myself of helper objects altogether. (As I write this, I’m still using a class of objects to represent taflmen—they’re inflated from the integer representation when needed, and compressed when the state is no longer active during a game tree search.) The first six bits of the integer are used for an ID number—each taflman-representation has a unique ID within its side. Six bits lets me define up to 127 taflmen per side, which is sufficient for every known variant, and leaves some room for busier alea evangelii variants, if desired. The next three bits define the piece’s type. I’m aware of five potential types of taflman: a standard taflman, a knight or a commander from berserker, a mercenary (a defending piece which switches sides when captured, seen in one proposed alea evangelii variant), and a king. Finally, the next bit defines whether the piece is a besieger or a defender.

I was a little put out to realize that my efforts did not actually buy me very much—I was still at about 15,000 states per second.

My next task was to observe the behavior of my code, and find out where it was performing poorly. An unexpected but obvious optimization presented itself. When you run a Java program, it defaults to using a small amount of memory. You can provide command line switches to allow it to use a much larger amount of memory. Doing that, I found I was up to 50,000 states per second—that’s getting somewhere.

In fact, that’s what I’d call having gotten somewhere. 50,000 states per second is sufficient to play a game of brandub to a search depth of 3, without undue waiting. (It takes about 40,000 states explored to get to depth 3, and about 1.2 million to depth 4.) I whipped up a quick evaluation function (which I’ll describe in a subsequent post), hooked it up, and quickly found that it played only slightly more poorly than I do5.

With that heartening development, I also stumbled upon a happy fact. Java is, at first, an interpreted language, but it compiles sections of programs to faster, native code when it discovers that it runs into them a lot. After the computer took its first turn, I saw the benchmark report that it had explored 200,000 states per second. 200,000 states per second I can live with—my laptop is several years old and a laptop, and in testing, my desktop was about five times faster in an earlier version of the code. I intend to test it again soon, and see what a powerful machine can do with it.

I made one final optimization after that. Since the AI code used a thick representation of game states, it was extremely memory-hungry—brandub to depth 3 took over four gigabytes of memory, and other games were impossible altogether. I solved that one with two changes: first, I now represent the explored nodes of a tree as a list of moves required to reach each node from the root. Second, I trigger garbage collection manually.

Now, this may seem like a bad idea, to those of you with some Java development experience, but in this case, it’s called for. The default Java garbage collection scheme is two-leveled: objects just created go in a group called the Eden space. The Eden space contains objects whose longevity is not known, and which will therefore likely be quickly removed. If an object survives garbage collection in the Eden space, it moves into the Survivor space, where middle-longevity objects live. The Survivor space is touched less frequently by garbage collection. Finally, if an object lives in the Survivor space through a couple of garbage collections, it moves into the Tenured space, where it is troubled by garbage collections least frequently of all.

A lot of my objects end up in the Tenured generation—the objects which represent boards, particularly. They’re long-lived and durable, while almost every other object in the code comes and goes somewhat quickly. That means that Board objects, which are rather large, and which also contain references to other, shorter-lived objects, stay in memory more often than I’d like, and keep their sub-objects in memory, too. Triggering a garbage collection manually garbage collects everything, regardless of the space in which it lives, so the Board objects are cleaned up, freeing space. It does slow the code down somewhat: I get about 120,000 states per second on my laptop now, under ideal conditions.

Like I said, I can live with that. It’s not where I want it to be, but it’ll do for the time being. Coming up in the not-too-distant future: writing on evaluation function, although I have some research to do before I’m done with that.

1. Go starts out branchier than 11×11 tafl variants, obviously, since you can play a stone at any point on the board. Thinking in terms of smart opening moves, I suspect the order still goes go, 11×11 tafl, chess. Large (that is, 19×19) tafl variants probably branch more than go at almost every stage of the game; the board is the same size.
2. That is, trimming unproductive branches from the game tree before expending the effort to explore them.
3. Here’s one for you. Computer memory is organized into bytes: eight slots to hold either 0 or 1 (called ‘bits’). Some data types are eight bytes long, or 64 bits. The chess board is 64 spaces, so someone had the idea to represent chess boards in a single eight-byte long integer. You need a few of these bitboards to represent a whole chess game state, obviously: minimally, two to represent which side controls each space, and six to represent which kind of piece occupies each space. Even so, it’s very compact, and bitwise operations on 64 bits at a time are blazingly quick on today’s 64-bit CPUs.
Unfortunately, this does not generalize well to tafl; most of the boards we concern ourselves with are larger than 64 spaces.
4. Namely, allowing black, using Berserker-style pieces, to jump into a Copenhagen edge fort to break it.
5. This says a lot more about me than about the AI.

Skypirates: lessons in zeppelin aircraft carrier design

Posted by

When I worldbuild, I put great importance on doing the background work, even background work which doesn’t feature in the foreground very often. So it is with zeppelins in the Skypirates world. Not only do we design them in the same modes and manners as real rigid airships, we’ve discovered that, to our surprise, they’re not quite as implausible as we thought.

Which isn’t to say that they aren’t implausible. We’re making a couple of assumptions rooted in our alternate history that are, well, unlikely. First: we assume that the limit on the size of airships was not one of 1920s and 1930s materials science, but rather one of insufficient ambition. Second: we suppose that engine technology in about 1925, owing to a few more years of the First World War to incubate, has reached levels not seen until ten or fifteen years later1. Third: we assume that large airships are much cheaper than they were in actuality, and that they’re much more common. Fourth: we assume a couple of highly-specific technological advances with respect to gas handling.

If you’re unfamiliar with airships, that last one might seem oddly specific, but it turns out to be critical. There are exactly two practical lifting gases2: hydrogen and helium. You may remember from high school science that hydrogen makes a tremendous *thump* as it blows up in the presence of flame. This doesn’t necessarily rule it out for zeppelins-of-war, but it does push it firmly into the realm of the sub-optimal. That leaves us with helium.

Helium is a pain. Its most notable characteristic3 is its mad delight in escaping every container you try to put it in, including Earth’s atmosphere. Its second most notable characteristic is its relative rarity. Because of its eagerness in leaving the planet once it’s free, there’s very little of it in the air, and it’s difficult to get out of the air. In the timeframe in which the Skypirates stories takes place, the United States historically controlled most of the world’s helium supply4, and, for political reasons, the Germans were unable to buy any for the Hindenburg. (And we all know how that turned out.)

Now, we also had another problem, not all that closely related, but ultimately in the same vein: aircraft-carrying zeppelins are heavy, and anything you put inside a zeppelin’s hull doesn’t just count against your total lift, it reduces it5. I’m going to introduce a term here, and I’m sure it’ll make airship engineers tear their hair out, but here we are: reserve displacement.

If you have a fixed amount of gas inside of a stretchable container, then reduce the pressure outside the container, the container will expand, and the pressure inside will drop. Although less air mass is displaced per unit volume, the container’s volume grows, and the container still makes lift. This effect explains why high-altitude weather balloons look tiny when they take off, and then get huge when they reach high altitudes. High-altitude weather balloons have high amounts of reserve displacement.

Rigid airships aren’t designed with lot of reserve displacement. Their gas cells start out almost fully inflated, for a very simple reason: over the course of a flight, airships get a lot lighter. Your choices are either to vent your lifting gas when you’re nearly to your destination, or rely on complicated ballast recovery systems to capture water vapor from your engine exhaust. One puts you at the mercy of the ground facilities at your destination6, and the other only works in the absence of heavy flight operations. Launching and recovering lots of planes is the same thing as dropping and taking on tens or hundreds of tons of ballast over the course of a few hours, and reality has no way to mitigate that.

So, we’re presented with three little plausibility concerns that get in the way of storytelling: zeppelins don’t have much room for gas cell expansion, limiting them to a narrow band of altitudes; realistic methods for landing require a loss of lifting gas unlikely to be available at your friendly neighborhood jungle ruin filling station; and air operations break all normal procedures for trimming and ballasting. We invented two pieces of retro-scientific fictional technology to gloss over those plausibility issues, both products of fictional Imperial German zeppelin pioneer Karl von Rubenstein.

The von Rubenstein cell is a specially-treated fabric gas cell with a fantastically7 useful characteristic: it is helium-impermeable (don’t ask me to explain it; I just said it’s fiction). von Rubenstein cells can be used as trim tanks, in a sense—if you limit a cell’s expansion, you can pump helium into it, and plain air into the others. The air-helium mix generates less lift per unit displacement, and the trim cell is holding more helium, but isn’t displacing any more air, and the lift goes down.

The von Rubenstein pump is what lets us move helium around so easily. Passing a mix of gases through its machinery yields helium as one output, and everything else as another. The air-helium mix inside a gas cell can easily be separated back into nearly-pure helium, thus raising the trim altitude again, and even atmospheric helium can be extracted, albeit slowly.

Combining the two, we have a model for airship operations. The secret is that modern zeppelins in the Skypirates world aren’t built with a lot of ballast. They’re built for a ceiling, with helium capacity and reserve displacement for that ceiling. In their untouched configuration, that’s their ‘trim altitude’—where they’ll end up, absent other concerns. To descend, or to land, or to launch aircraft, the crew pumps extra helium into the trim cells, and the zep’s lifting capacity goes down.

Practically speaking, there are a few inescapable limitations. For one, a zeppelin’s initial trim altitude—its pressure height, as the technical term goes—is inversely related to its lifting capacity. To leave room in the gas cells for high-altitude expansion, the gas cells must not be filled at sea level, and doing so leaves buoyancy on the table. To some degree, trim cells mitigate this—the excess can be pumped in and held at pressure, and eventually the reduced amount of helium in the lift cells will balance out the zeppelin’s weight, or either trim or lift cells will explode8. Between that and limited ballast, though, we have the ability to let our zeppelins cruise at a broad range of altitudes, which was our aim in the first place.

Another of those inescapable limitations comes from structural strength and weight. It strikes me as unlikely that zeppelins of the bulk we’re talking about could be built as lightly as we say the are. Assuming I’m wrong, we’re within about 10-15% of actual, possible zeppelin designs, in an ideal world, with our fantasy technologies. If I’m right, the figure is more like 25% or 30% off, I’d wager.

Even so. When I first went over the design rules parvusimperator found for zeppelins, I thought to myself, “This is awesome, but utterly impossible.” From ‘utterly impossible’ to ‘we just need to be about one-third lighter than aluminum actually is’? That’s progress.

Expect a few more posts on zeppelin design in the near future. For one, I’ve completed a first draft of a vaguely technical cutaway drawing of Inconstant, which may eventually show up on a mug, and I want to go over it some. For another, I mentioned the zeppelin construction rules, and I feel like I should provide those, too, pending parvusimperator’s approval.

1. This is not zeppelin-specific, but it does explain our extreme fuel efficiency.
2. Impractical lifting gases include water vapor, ammonia, methane, simple hot air, and (yes, I know it isn’t a gas) vacuum, all of which don’t work in large airships for various reasons.
3. Besides being lighter than air and making your voice funny when you inhale it, that is.
4. It comes from natural gas wells, mostly.
5. Airships work by displacing air with a lighter lifting gas. When you’re putting aluminum hangar plating or a library in the place of gas cells, you’re cutting into your displacement.
6. “Top me up! I need about five hundred thousand cubic meters!”
7. In the sense of fantasy, too.
8. This is bad.

A change in comment policy

Posted by

Because I’m much too lazy to make and link comment threads reliably, comments are now open by default on new posts. (We still reserve the right to close comments on certain posts for which ‘blog comment thread’ is the wrong venue for a productive conversation, but really, we mostly talk about procurement stuff right now, and on that topic, we already disagree pretty diametrically.)

Hopefully you’re more guilty now to leave a post uncommented. 😛

On tafl: AI basics

Posted by

My last tafl post was deeply theoretical. Very shortly, this one is going to take a turn for the deeply practical. First off, though, there’s some theory housekeeping I need to handle. Because the Copenhagen and Fetlar variants are both difficult AI problems, and because Copenhagen has some additional rules which are computationally hard to check, I decided to start with brandub, a much simpler tafl variant. Brandub comes from Ireland, and is played on a 7×7 board. The king’s side has five pieces, and the besieging side has eight, arranged in a cross. The king participates in captures, and is captured by two besieging pieces instead of four. He escapes to the corners. Any piece may cross the center square, but only the king stops on it.

Computationally, brandub is in a much easier class than the 11×11 variants I’ve discussed. The upper bound on its state space complexity is a mere 4.4 x 1015, using the estimation technique I described in the previous post; for comparison, checkers1 is on the order of 1020. Its game tree complexity is at least 1.3 x 1036, which is also not overwhelmingly distant from checkers’ complexity (though harder—tafl’s state space complexity is frequently lower than comparable games, but its game tree complexity is frequently higher). This makes it a good place to start—for one, it means that it doesn’t matter how slow my code runs.

So, to kick things off, I started with what the business calls GOFAI—good old fashioned AI—techniques. The simple version is this: you play every possible move from your current position to a few moves out, and pick the best outcome. It ends up being a little more complex than that, though. If you’re not curious, you can skip the next few paragraphs.

The particular GOFAI technique I’m using right now is a straight implementation of the minimax algorithm. After generating a game tree from the current state to a given search depth, the algorithm evaluates the tree’s leaf nodes. An evaluation is a single number, describing whether the state is good for the besieging side (nearer positive infinity) or good for the defending side (nearer negative infinity). The details aren’t important just yet, although I’ll get into them later. Anyway, the algorithm is predicated on the assumption that both players are perfect—they’ll always make the best move they can make, given the situation. It follows, therefore, that the best move at a certain depth is the one which leads to the best state for him: the most negative for the defender, the most positive for the besieger.

As an example, with the besieger to move and a search depth of three, there are four levels to the tree2:

1. A position with the besieger to move.
2. All of the positions, defender to move, resulting from every one of the besieger’s possible moves.
3. All of the positions, besieger to move, resulting from the defender’s possible responses to those moves.
4. All of the positions, defender to move, resulting from the besieger’s responses to the defender’s responses.

The algorithm starts at the tree’s leaves, the nodes at the fourth level above, and runs the evaluation function. It then moves up a level. The besieger is to move, and all of his possible moves have a child state which has an evaluation attached to them. The besieger picks the move which yields the best outcome for him, which is also the worst outcome for the defender. (Although the tafl board is asymmetric, the game, in the theoretical sense, is not—a good state for the defending side is a bad state for the besieging side, and vice versa.) The value of each node at the third level becomes the value of its best child (for the besieger). The algorithm then moves up to the second level. The defender is to move, and he has a set of moves and child states with evaluations attached, as we just derived. He picks the best outcome for himself, which is also the worst outcome for the besieger. The value of each node at the second level becomes the value of its best child (for the defender). The algorithm then moves up a level, and, at the first level, the besieger has a list of moves and child states with evaluations attached to them. He chooses the best move out of his options, and that’s the move he makes.

As you might have guessed, if you had a computer of infinite power, you could just explore the game tree until you found a win, loss, or draw for every sequence of moves from your starting state. In fact, we call games for which this is possible3 solved. The evaluation function for an infinitely powerful computer is extremely simple:

1. Has the besieger won in this state? Return positive infinity.
2. Has the defender won in this state? Return negative infinity.
3. Has neither of the above happened? Return zero.
4. Ignore draws for the purposes of this example, or declare them a win for one side, or something.

The algorithm will explore until every branch reaches an end state, then work its way up through the tree. Since it assumes perfect play, it will provide a sequence of moves which yields a victory for one side from the current position, and there’s nothing the other side can do about it—the whole game becomes inevitable. Perhaps fortunately, this is extremely hard for most games; tic-tac-toe is somewhat less thrilling now that it’s solved.

It also reveals a weakness in, or at least a caveat with, the minimax algorithm: since we do not have computers of infinite power (in fact, my current implementation is able to look ahead only one ply further than the example I gave above), its playing ability depends either on achieving deep lookahead to compete with humans, who can look ahead much more selectively than computers can, or on having a good evaluation function. I haven’t really attained either goal yet.

I see that I’ve already written about a thousand words, and I haven’t even made it out of the first point on my supposed outline for this post. I suppose I’ll just have to write a couple of ’em. Next time I’ll get into the practical considerations in implementing an AI algorithm like this. Probably the time after that, I’ll write about evaluation functions, and perhaps after that I’ll write about some improved algorithms. The latter requires that I actually implement them, though, so we’ll see how the timing works out.

1. 8×8 draughts, if you aren’t an American.
2. The term of art is ‘plies’, singular ‘ply’—since a response to a move is called a reply, clearly a single move must just be a ply. (Math and computer people, am I right?)
3. Wikipedia has some interesting reading on what it actually means for a game to be solved—the definition I’ve given is what’s referred to as a ‘strong’ solution, where a computer has brute-forced the entire game tree. There are two other kinds of solved games: those solved ‘ultra-weakly’, which is to say, by abstract mathematical reasoning, and those solved ‘weakly’, by some algorithm which does not explore the entire tree.

Pacific War and the recipe for compelling wargames

Posted by

Pacific War

This is Pacific War, a 1992 release by Gary Grigsby. I’ll come back to that.

I’m on something of a Pacific Theater kick, for an unusual reason: over at the Something Awful LP Archive, I’ve been reading an AAR by a guy called Grey Hunter. The game is War in the Pacific: Admiral’s Edition, the Grigsby/Matrix magnum opus, covering the whole war in excruciating detail. It’s the kind of thing I would love, if I wanted to drop the $80 on the price of entry, and the several hundred hours it would take me to actually get through the war. Fortunately, I can read the 1,320 entries in Grey Hunter’s AAR much more quickly than I can play the game myself, and so get a feel for the flow of things more than the day-to-day minutiae of supplying the twelve-man garrison on Rarotonga. I’ll come back to that.

One of my favorite wargames, as you’ll know if you follow Many Words Main in the slightest, is the Command Ops series. Its conceit is that, as the player, you have to deal with all the handicaps real field commanders had to deal with. Your orders have to percolate down to your subordinate commanders, and hours pass as they dawdle (from your perspective) to plan a simple attack on a defensive position. You tear out your hair, watching the map as they miss the enemy battalion just behind the hill and happily claim success after wiping out a poor company of engineers. You celebrate your own cunning when your men just finish setting up when an enemy attack lands. It is, as the title says, a compelling wargame. But what does that mean, really? ‘Compelling’ is one of those review words1 that doesn’t mean anything absent a better definition. Let me explain what I’m trying to convey.

Ian W. Toll, one of my favorite naval historians2, wrote a book about the first six months of the Pacific War. I’ve always regarded Toll’s biggest talent as immersion. He writes vividly, with a knack for putting the reader into the mind of the people who were there. Near the beginning, he quotes Chester Nimitz, on his experience in the first few months of the war: “From the time the Japanese dropped those bombs on December 7th until at least two months later, hardly a day passed that the situation did not get more chaotic and confused and appear more hopeless.” That gets at the crux of it, I think. I’m still in the first few turns (weeks) of my game of Pacific War, and I don’t think I’ve ever felt more despairing while playing a game. The deck is stacked so heavily against the Allies in the opening weeks: the Japanese are everywhere, and you categorically lack the planes, men, and ships to do anything about it. It has a very strong sense of place, and that is compelling. Command Ops has it, too: in the AARs in the archives at Many Words Main where I follow along in a history book, I find myself worrying about the same sorts of things as commanders on the field did. I find myself feeling exactly how CINCPAC Nimitz did.

I mentioned I’d be coming back to War in the Pacific. As I hinted, I don’t own the game, and I’ve never tried it. It’s possible I might find it compelling in the same way, but reading through Grey Hunter’s AAR, I think it’s not a settled thing by any means. In the course of spending forty-five minutes to an hour working through a single day, I think I might lose sight of the bigger picture, and games about the Pacific War are ultimately games about an entire theater. The sense of place flows out of watching the long arc of progress, and at a certain scale, that’s hard.

So, for me, compelling wargames capture a sense of place. That doesn’t preclude them from being grognardy, but it does preclude them from swamping the feel with detail. Pacific War is just about right, I think—accurate enough to yield plausible results, broad enough in scope to engender the emotional investment I crave.

Pacific War is freeware, courtesy of Matrix Games. You can find it at their website, or at my mirror.

  1. See this video, starting at about 3:00, or 4:30.
  2. Objection, your honor. Relevance3.
  3. Overruled. I want to see where this is going. Counsel, make your point quickly.

On tafl: state space complexity

Posted by

One of the most basic ways to describe the computational complexity of a game is its state space complexity—that is, the number of unique positions possible for a game—and that’s where I’ve started in my analysis of computer tafl. For now, and probably for every post I write on tafl and mathematics, I’m going to stick with Fetlar rules tafl or Copenhagen rules tafl1, on an 11×11 board.

To start off, we can make an extremely, extremely rough estimate. The board has 121 spaces, and each space can be empty, occupied by a besieger, occupied by a defender, or occupied by the king, so to get an absolute upper bound, we can just do this:

4^{121} \approx 7\times10^{72}

7 x 1072 is surprisingly close to the rough estimate for chess (1.9 x 1071; chess has thirteen states per space and 64 spaces). We know the actual state space complexity of chess to be in the vicinity of 1047, however, so we can clearly do better. And, if you think about it, we’re not even trying all that hard. Our current estimate permits some flagrantly illegal positions, like a board entirely filled with kings, or the board with no taflmen.

There are plenty of obvious constraints we can use to tighten up our guess. For one, any reachable tafl position has to have at least three taflmen: one side must have two taflmen, to have captured the second-to-last piece from the other side, and the other side must have at least one taflman left, or else the game is over. For another, there are only 37 taflmen to place.

An intermediate question presents itself: in how many different ways can three to 37 taflmen be placed on 121 spaces? Well, that’s a question for combinatorics. For any number n of taflmen, the number of unique arrangements of those taflmen into 121 spaces is:

\binom{121}{n}

And, since I’m a programmer, and loops come naturally to me…

\displaystyle\sum_{i=3}^{37} \binom{121}{i} \approx 3\times10^{31}

So, we have 3 x 1031 ways to arrange our taflmen onto our board. Going forward, I’ll multiply it by one quarter2, although it hardly matters at this scale3. This picture is also incomplete—it’s not an upper bound, because it doesn’t account for taflmen belonging to the besieging or defending sides. For every arrangement of n taflmen on the board, there are a bunch of distributions of the taflmen between the besieging and defending sides, and a bunch of options for the position of the king within the defending side.

So, since I am still a programmer, time to break out the nested sums. For every number of taflmen i between three and 37, consider the distribution of taflmen between the sides. For valid positions, let k be the number of pieces on the defending side, between one and i – 1. We need only consider one side. From a logic perspective, it’s obvious why: answering the question, “How many ways are there to assign k taflmen to the defending side?” contains in its answer the answer to the question, “How many ways are there to assign i – k taflmen to the besieging side?” Since the two sides exist on the same board, the number of defending positions is the number of attacking positions. (There’s a mathematical argument in a footnote4, if you don’t buy this.)

Anyway, that insight gets us most of the way there. We have one more thing to account for: the position of the king. One of the defending taflmen must be the king for this position to be valid, and the king is distinct from every other defending taflman. Any one of the k defending taflmen could be the king: that is, there are always exactly k distinct arrangements of the defending taflmen for any distribution of taflmen between the sides, so we multiply the two numbers together.

\displaystyle\sum_{i=3}^{37} \Bigg(\binom{121}{i} \times \bigg(\sum_{k=1}^{i-1} \binom{i}{k} \times k\bigg)\Bigg) \\[1em] \approx 1.4\times10^{43}

There we have it: the number of possible arrangements of taflmen on the board for every valid number of taflmen, multiplied by the number of ways to split a certain number i of taflmen between each side, is a much better bound on the number of possible positions. It’s still not perfect: mainly, this model permits some positions where pieces have illegally stopped on restricted spaces, and I’m probably missing some other things, too, but it’s a close enough bound to make an interesting point.

11×11 tafl games have an upper bound on state space complexity on the order of 1043. Chess, as I mentioned earlier, has a state space complexity on the order of 1047. This might seem like evidence against my theory that tafl games are more computationally complex than chess, but I’m still convinced. Ultimately, state space complexity is a poor measurement of computational difficulty. Consider backgammon: its state space complexity is on the order of 1020, but backgammon AI is a more difficult problem than chess AI.

There is another metric to introduce: that of game tree complexity. State space complexity measures the number of possible positions for a given game. Game tree complexity measures, in a sense, the number of ways to get there. Consider a tree of every possible game of tafl. You start, obviously, with the starting position, then create a leaf node for every possible move by the defending player. At each of those leaves, create leaf nodes for every possible response for the defending player, and so on until every possible combination of moves has resulted in a game-ending state. (We’ll assume there are no ways for games to go on forever.) The number of leaves at the bottom of the tree is the game state complexity.

This number, Wikipedia remarks in its typical laconic style, is “hard even to estimate.” This is true. Wikipedia also remarks that a reasonable lower bound can be established by raising the branching factor, the average number of moves possible at any given step, to the power of the game length in plies (that is, one player moving once). This is where things start to get interesting.

The accepted figure for chess’s branching factor is 35. From the starting position, each player can make 20 distinct moves. (Pawns forward one or two squares, or knights to the inside or outside.) Chess games last, on average, about 40 turns, or 80 plies. The game tree complexity of chess is at least 10123. Backgammon’s branching factor is 250, and its average game length is about 60 plies, so its game tree complexity is at least 10144.

I don’t have a figure for tafl’s branching factor. Aage Nielsen’s tafl site has a tournament running right now, using the Copenhagen tafl rules. Once it’s finished, I’ll look at some positions from the midgame and the endgame and try to work out a good average. In the interests of providing a number, I tweaked OpenTafl’s debug script to print out a count of the number of possible moves on the opening turn. The besiegers can make 116 moves, and the defenders can make 60, for an average of 88. High-level tafl games seem to go on for about 40 turns or 80 plies, from my observation so far. This yields a lower bound of 10167, which rather blows chess out of the water.

Let me try to contextualize that number. Relatively simple 11×11 tafl games are, as far as I can tell, more computationally difficult than any historical abstract strategy game besides go. Not only that, but larger tafl games (15×15 or 19×19 variants) seem likely to me to be more difficult than go.

If you’re not well-read on the subject of board game artifical intelligences, you may have missed what a crazy thought that is. Go is the benchmark for hard AI problems. Computers were playing chess and backgammon at grandmaster levels by the end of the 1970s. Computers still can’t beat professional go players in even games, and the hard tafl variants are probably harder than that.

This is a seriously cool game.

1. Here are rules for the Fetlar and Copenhagen variants. If you don’t care to read them, here’s the summary: they’re more or less identical for my purposes here, played on an 11×11 board with 12 defenders, one king, and 24 attackers.
2. Think about it: any arrangement of taflmen on the board is functionally identical if you were to rotate the board 90 degrees beneath them in either direction, or 180 degrees.
3. Remember, with scientific notation, 8 x 105 divided by four is 2 x 105. Or, indeed, 8 x 100 divided by four is 2 x 100.
4. Let i be the number of taflmen on the board, k be the number of defending taflmen, and i – k be the number of besieging taflmen. The number of distributions of taflmen for the defenders is:

\binom{i}{k}

Therefore, k taflmen have already been accounted for—the besieging side can’t choose them, because they’ve been chosen as defending taflmen. We do not choose from i, we choose besieging taflmen from from i – k, which yields:

\binom{i - k}{i - k}

Which is one, and can be simplified out.

On the only fitting and manly response to thrown gauntlets

Posted by

Whereas, Fishbreath is neither a lazy shirker nor a poltroon; and
Whereas, Fishbreath is nevertheless a busy man; and
Whereas, Parvusimperator ought not escape the difficulty of deciding on things (or at least writing articles to justify those decisions),

Be it resolved that Fishbreath demands to see the following things from Parvusimperator:

1. His choice for a short- to medium-range air defense system, bearing in mind that he cannot buy Russian;
2. His choice for an APC;
3. His choice for an anti-tank rocket (i.e., for the AT specialist in a rifle squad), and an infantry-portable ATGM (for a proper AT team).
4. His 25-year, $250 billion procurement budget, as submitted to Borgundy’s legislature. (In the spirit of fairness, I’ll come up with one, too.)