Monthly Archives: April 2015

On tafl: game tree search optimizations

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.


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.

AAR: M&P40 Project

This is a new one for me–I’m talking about the results of a project gun rather than the planning phase. So I’ll try to give you planning bits too, but they’ll almost certainly be hindsight tinted. I’ll also make this partially a review, but that’ll be hard to do because I do love to tinker, and this is hardly a stock pistol anymore.

I picked up a Smith & Wesson M&P40 for a few reasons. I had given them a shoot over at the Gander Mountain Expo, and rather enjoyed the experience. Plus, I wanted to try something a little different from the usual “Glock 9mm” that I had tended to shoot up to that point. I debated the M&P in 9mm, but those had some issues in the not too distant past. The M&P was designed first for the .40 S&W round though, and those hadn’t had problems. Plus, I always wanted to give the .40 S&W round a try, and what better platform to do it with?

The .40 S&W round is an interesting one. It occupies an intermediate position between 9mm and .45 ACP. You get more rounds in the mag than you would with a .45, but you give up a couple to a 9mm pistol. It can still fit in a 9mm frame though, so those of you with small hands won’t gripe as much about fit. Oh, and the .40 S&W is a hot round. The .40 S&W grew out of the 1980s dissatisfaction with .38s and 9mms from the FBI. Initially, the FBI went with the 10mm auto, but this required the same sort of big frame as a .45, and was a really hot round. Female shooters and the recoil averse weren’t very happy, so the FBI had ammo makers make them a lighter loaded 10mm auto. From there, someone realized they could shorten the case somewhat and fit it in the same frame as a 9mm, and thus the .40 was born. It’s a super popular round for law enforcement. Modern ballistics being what they are, 9mm hollow points have caught up, and now (joy of joys) you can get good hollow points in all major calibers that pass the FBI gelatin tests. 9mm has a small advantage in magazine capacity, and is a bit cheaper. But there’s nothing wrong with .40; it certainly won’t get smaller when it hits something. It maintains it’s energy edge, and some have called it ‘snappy’ or ‘hard recoiling’.

When Smith & Wesson decided to challenge Glock properly in the polymer-framed striker-fired pistol market, the resurrected one of their most storied brands: M&P. The original Military and Police, also known as the Model 10, was an extremely popular service revolver for police officers and various militaries, as well as being a popular pistol in the civilian market. It’s the most popular centerfire revolver of the 20th century, with some six million being made. There are a number of things to like about the current-production M&Ps from design and user standpoints, and I also have a couple gripes.

First, the good stuff. The M&P is wonderfully comfortable in the hand. The interchangeable backstraps are the most comfortable that I have played around with1, and they do a really good job of accommodating various hand sizes. The backstraps change both length and width of the grip, which is super helpful. The backstraps are held in place by a handy pin/tool thingy that is inserted into the bottom, behind the magwell. We’ll get to this later, but it’s pretty handy to always have a gunsmith manipulation tool with your pistol. The slide stop is ambidextrous, and it’s well positioned to be far enough back to be easily reached with your strong hand thumb, but not so far back that you might be tempted to rest your thumb on it and prevent the slide from locking back on an empty mag. It’s also not so far forward that you might rest your support hand thumb on it and do the same thing. Sizewize, it’s big enough to be easy to manipulate, but small enough that you don’t hit it accidentally. It’s a really solid design. I’ve also noticed that it drops the slide automatically if I insert a full magazine with gusto. I’m not sure if this is a design feature, but I like it.

There are a whole bunch of minor things that I like too about the M&P. The slide cocking serrations are really good. They’re sort of a fish-scale design, and they’re quite grippy. I really like grippy. Plus, they look cool. Also, in the minor details that I like column is the dovetailed front sight. I much prefer front sight dovetails to the stake/screw method, especially when you put nice aftermarket sights on your pistol. Dovetails are the way to go. I also rather like the rotating takedown lever much more than the pull tabs of Glocks or HKs. It’s a really little thing, but hush, I still like it. One of the niftier little things is a small internal lever (that you can trip with that tool in the back of the grip) which is used to release the sear for disassembly so you don’t have to pull the trigger. Since plenty of accidental discharges occur on the disassembly phase from complacency, I sort of like this feature. Even though I tend to disassemble my M&Ps with a trigger press, because I’m lazy.

Safetywise, I got my M&P just like my Glocks: No external safety. Since they’re going for the law enforcement market though, Smith and Wesson is nice enough to let you choose what safeties you want. If you’re like me, and don’t like external safeties, you don’t have to get them. If you’re like Fishbreath, you can get them on your M&P, and they’re even frame mounted as God and John Moses Browning intended. If you’re mental, or an overly-paranoid police department, you can also opt for a magazine disconnect safety in addition to the external safety (or lack thereof). Fishbreath and I do agree (you’re shocked, I know) that magazine disconnects are stupid.

So the M&P feels good in the hand, and has a bunch of nifty features. What don’t I like? Well, two things. One is minor: the mag catch. Or more precisely, the bit of plastic behind the mag catch. It makes me reach a little more to get to it, and makes pressing it a little uncomfortable. It’s a really minor gripe, I know, but it bothers me. I’ve ordered up an extended mag release, and that’ll probably fix it. More troublesome is the trigger: it’s not very good. The stock trigger has a rather mushy takeup, a really hard wall to release the sear, and then a soft, weak reset. UGH. While I could send it off to a gunsmith, it’s much easier to buy an Apex trigger kit and put it in yourself. The end result is a trigger with more pretravel than a Glock, but a very respectable reset and a somewhat less obnoxiously wall-like break. The Glock trigger is still a trifle better, but that might be just because my test glock at hand has lots of rounds through it, polishing everything up inside the slow and fun way. Without the Apex kit, the M&P trigger is annoying. With it, it’s a pretty good polymer service pistol trigger. It’s nowhere near as good as my 1911, but it was a whole lot cheaper too. It does bother me that S&W can’t make their triggers suck less though, but it’s a simple fix away.

I should also point out a significant advantage of the M&P (and to an even greater extent: Glock): ubiquity. These pistols are everywhere. Finding parts, accessories, or a factory certified armorer is easy. Magazines are cheap. And new sights come to you first. Finding holsters is easy. It lets you pick what you want to experiment with, and run the gun the way you want to, rather than the way that you can find accessories to accommodate you.

So let’s go over the pistol. I’ve already mentioned that I put an Apex trigger kit in. Specifically, it’s the duty/carry kit. There’s also a competition kit available if you want a lighter trigger. Fringe benefit of installing this myself is that it really helped me get a good understanding how this pistol (and other, similar striker-fired pistols) work. It wasn’t a very hard install. I also am going to try out an extended mag release, see how that goes. I also sent the slide out for milling to install an RMR. Why RMR? Because it’s tough. It’s built right. The adjustment dials are in good places, and battery life is excellent. I had the milling done by Mark Housel of L&M precision, and he did a really great job. I also have suppressor-height Ameriglo iron sights mounted as backups. These are there in case the battery dies at a bad time, or Murphy and his law find a way to make a bother of themselves. They also help find the dot if my presentation isn’t good.

I’ve already discussed the mini red dot academically; now I’ll talk about what I’ve found. The red dot will make any issues in your draw and presentation painfully obvious. It’ll also wobble a bit, picking up on all those tiny little twitches. And, it slows you down initially, because you’ll often find yourself wondering, “where the hell did that stupid little dot go?” But after some practice, I found that it made me faster. It made me more accurate. It helps in dry fire, because it makes errors in your trigger press a lot harder to ignore and ‘cheat’ through. Oh, and if that’s not enough of an endorsement, I sent another slide to Mark to work his magic on.

1. I’ve heard HK and Walther’s newer designs are as comfortable as the M&P, if not more so, but I don’t have serious time on either, so I could not possibly comment. A PPQ of some flavor is probably the next pistol I get though, judging by all the rave reviews its trigger gets. So stay tuned.

Skypirates: lessons in zeppelin aircraft carrier design

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.

M1 Variant Naming Silliness

Fishbreath and I often like to laugh at the Russians and the goofy naming conventions that they have for things that have been produced a lot, like the T-55, the T-72, or the Su-27. That said, they’re not the only ones to do it, and the naming schemes for my favorite tank, the M1 Abrams, are particularly annoying.
Here they are, in order (ish) of when they were first made.

M1A1AIM v.17
M1A1AIM v.28
M1A2SEP v.215
M1A2SEP v.2 TUSK16
M1 TTB18

1. There were two rather different prospective designs for the M1, one made by GM and one made by Chrysler. Both designated XM1 for the trials to see which was best. Figuring which XM1 is which is an exercise left to the reader, who will no doubt find it enlightening.
2. IP for ImProved.
3. -HA for Heavy Armor, i.e. it’s got first generation depleted uranium armor.
4. M1A1HA subsequently upgraded with second generation depleted uranium armor. Unofficial, but included for completeness.
5. -HC for Heavy Common, i.e. made with second generation depleted uranium armor.
6. -D for Digital. An M1A1HC upgraded with electronics to the M1A2 standard. No factory reconditioning is expressed or implied by this designation.
7. AIM for Abrams Integrated Management. Earlier model factory reconditioned to be like-new, and then a whole bunch of electronics are added.
8. As -A1AIM v.1, but also upgraded with third generation depleted uranium armor.
9. -SA for Situational Awareness. As -A1AIM v.2, but with a confusing new name. See -A1AIM v.2.
10. -FEP for Firepower Enhancement package. As -A1SA, but for the USMC. See -A1SA.
11. -KVT for Krasnovian Variant Tank. M1A1 modified to look like Soviet tank for training purposes.
12. Export variant for Iraq. Because they got their butt kicked twice by Abrams tanks, so they figured they might as well buy some.
13. SA for Special Armor. Export variant for Morocco. Not to be confused with the other M1A1SA.
14. -SEP for System Enhancement Package. Adds third generation depleted uranium armor and some improved electrical systems.
15. Even better electrics.
16. TUSK for Tank Urban Survival Kit. Makes the tank better suited for urban warfare. Technically, may be applied to any variant. Usually seen applied to A2, A2SEP, and A2SEP v.2s.
17. TUSK II has better supplemental armor than TUSK.
18. Tank Test Bed. M1 variant used for a bunch of late 80s experiments.
19. Component Advanced Technology Test Bed. A more-radical, experimental, late-80s tank.
20. The Grizzly Combat Mobility Vehicle. No, I can’t use the name again because that’s not the designation. I didn’t write “Abrams” after every designation up there, did I?
21. Wolverine assault bridge.
22. Panther II Mine Clearing Blade/Roller System.
23. The Assault Breacher Vehicle25.
24. Armored Recovery Vehicle. No, roles do not count as part of the designation, or else I would have written “MBT” after a whole bunch of things up there.
25. What’s the difference between Combat Mobility Vehicle and Assault Breacher Vehicle? No idea.

A change in comment policy

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

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.