In which we have no special theme for you, but we do have: a squee-worthy news topic immediately following a weighty warlike one, some further competition kit chit-chat, some defenses of indefensible procurement errors, and a proper savaging of a game that we describe as, “Factorio, but boring,” as well as, “EVE Online for shut-ins”. Listen and see for yourself.
Undoubtedly the release number will continue to increment as I find and fix little bugs in my work on the AI improvements branch. Either way, v0.4.2.x is now the stable branch, carrying with it two major features: variations in replays, and some additions to the stable of rules.
First, variations: the headline feature for v0.4.x, variations provide players the ability to play out alternate histories in replay mode. These alternate histories can be saved and loaded, as well as annotated (and, annotations now have a handy new in-game editor for ease of production).
Second, rules: I finally got around to implementing the last two rules preventing OpenTafl from playing almost all known tafl variants. Not coincidentally, OpenTafl now supports every rule supported by PlayTaflOnline.com, so the bot player there can compete on every front. Poorly.
That brings me to my last point for today: AI improvements. What’s on the list? Well, I have a few things on my list.
First thing’s first: I have to characterize OpenTafl’s particular failings. The ones I can most easily fix rest in the evaluation function. If the evaluation function provides inaccurate evaluations of board states, then all the rest—heuristics and fancy pruning alike—rests on an unsteady foundation. The analysis engine feature aids me in this quest. My workflow for this initial phase goes like this: I play a game against the AI, using the analysis engine to feed me the AI’s moves. When the AI makes a move which is obviously bad, I go to the replay, then tell the analysis engine to dump its evaluations for the states in question. By comparing those evaluations with evaluations of the move I would prefer, I can begin to see what the AI sees.
I’ve already made two interesting discoveries regarding AI weights and preferences. First, it places far too much importance on guarding or attacking the king, to the point that the attacker AI will happily sacrifice piece after piece if only it puts the king in ‘check’. Second, flowing out of the first item, it has a badly inaccurate view of what constitutes threatening an opposing piece. When it decides to threaten an enemy piece, it will happily do so by moving one of its own pieces into a position where it can immediately be recaptured. Oops.
So, once I’ve made changes to fix those mistakes, how do I verify that I’ve made a positive difference? I play the AI against old versions. Thankfully, building older versions of OpenTafl is trivial. (If you’ve been following development, you’ll no doubt have noticed that there’s a Mercurial tag for every release.) I have a little tool which is intended to do Elo ratings for chess clubs, but which will serve to do Elo ratings for OpenTafl versions just fine. This helps quantify not only whether a version is better than another version, but by how much.
Once I have the evaluation function a little more settled, I can move onto some extra heuristics. I have two in mind for the moment: the killer move heuristic, and the history heuristic (or some related heuristic). The killer move heuristic is the more promising one. It assumes that most moves don’t change the overall state of the board too much, and there are likely to be, at a given depth in the tree, only a few plausible moves to push the evaluation in your direction. Therefore, if any of those moves are possible at that depth, the AI should try them first.
The history heuristic is more complicated. There are three variations I’m considering. First, the straight history heuristic, which orders moves by how often they’ve caused a cutoff. This prefers, in the long run, making moves which have been good elsewhere in the tree. Straightforward, compared to the others.
Second, the butterfly heuristic, which orders moves by how often they occur anywhere in the tree. This prefers making moves which are frequently considered. This one is a little more subtle. Alpha-beta search, by its very nature, ends up searching only the most interesting moves, pruning away the rest. The butterfly heuristic, by tracking moves which turn up a lot, is essentially tracking which moves are more interesting.
Finally, the countermove heuristic, which tracks which moves are the best responses to other moves, and weights moves matching the known good countermove more heavily. This one requires very little explanation.
So, in the next month or two, I expect the strength of OpenTafl’s AI to improve considerably. Stay tuned!
The headline feature in OpenTafl v0.4.x is playable variations: that is, when viewing a replay, you’ll be able to say ‘variation a1 a3’ to create a new branch in the history, which can be added to, viewed, navigated, and commented upon like any other branch. It turns out this is, to put it mildly, non-trivial. Before I go into why this is, I’d like to talk for a few hundred words about why this feature excites me.
In short, this feature is the last feature before OpenTafl hits feature-completeness, relative to engines for other abstract strategy game engines. Other engines include it because it’s a useful tool for teaching and review; OpenTafl will be no different. I find teaching, especially, to be important. At present, available tafl commentaries remark only on the principal line of play. If they touch on variations, they do so only in passing. Understanding why a variation is a bad idea is all but a requirement for higher-level play, and providing room for commentators to make those comments is therefore a requirement for OpenTafl.
The usage in which I’m most interested, however, is puzzles. A puzzle is nothing but a branching commentary in which it is impossible to read ahead, and OpenTafl should support that pretty easily. I have a few tafl puzzles in mind already, thanks to interesting situations from my approximately-weekly game, which I hope to package with the first release of v0.4.x. To fulfill the ‘impossible to read ahead’ requirement, I’ll be adding an allowable tag to the saved game file format. When set, OpenTafl will suppress use of the ‘history’ command when viewing a replay.
Both of these usages presuppose a community of OpenTafl-literate commentators and puzzle authors, and the current setup for editing commentaries is not what you would call user-friendly. I plan to stick in a quick-and-dirty comment editor, a big text box you can use to define the comment for a particular state.
There. That covers, approximately, the list of features and their justifications for this release. On to the depressingly practical bits. How?
It turns out to be a tricky problem. I did not write the early versions of OpenTafl with an eye toward a tree structure for game histories. Since the GameState object, the standard representation for a tafl position in OpenTafl, is already a heavy object and already used in the AI, I didn’t want to add anything further to it. OpenTafl already uses a ReplayGame object to overlay the basic Game object during replays, so the natural thing to do was extend GameState to ReplayGameState, and put all the replay-related data and functionality into ReplayGameState. This solved the first problem: where to store the data? It revealed another: how to reference it?
It turns out that the problem of naming branches in a tree is also not altogether trivial, at least as far as the scheme goes. Fortunately for you, OpenTafl user, you won’t have to worry about figuring out how it works; replay mode will name each state for you, and you can specify which one you want to jump to. I, however, had to do the heavy lifting.
In replay mode, each state now has a specific name. The first state (more accurately, the first move) is state 1a. The next move is state 1b. (In berserk tafl, you might see a 1c or a 1d.) Those two (or more) moves compose the first turn. Turn 2 comprises 2a and 2b. Easy so far, right? Let’s dive into a more complicated example. Say you start a game, enter replay mode, and type ‘variation a4 a2’. You’ve now moved off of the beaten path: you’re in a variation. The state you’re in is now called 1a.1.1a.
Whoa. What’s going on?
This is an OpenTafl variation address. We’ll read them from right to left. First, the last element: 1a. That means this is the first turn of a new branch of play, and this is the first move therein. Next, the middle element: 1. That means that this is the first variation off of the state to our right. Finally, the first element: this variation replaces move 1a. A shorter reading is, “the first move of the first variation off of move 1a.” If you make further moves in that variation, they’re called 1a.1.1b, 1a.1.2a, 1a.1.2b, and so forth. For the sake of clarity, we’ll start some of our later examples from 3a, and its first variation: 3a.1.1a. (The first move in the first turn of the first variation off of the first move of the third turn.) Got it? Cool. We’ll try a harder one.
7b.3.1b.2.4a.1.1b. (I said it would be hard.)
Remember, right to left. This is (1b) the second move in the first turn of (1) the first variation off of (4a) the first move of the fourth turn of (2) the second variation off of (1b) the second move in the first turn of (3) the third variation off of (7b) the second move of the seventh turn of the game.
Those of you quicker than me will have noticed something a little odd. Remember how I said the first move following 3a.1.1a is 3a.1.1b? Well, what happens if we make a variation off of 3a.1.1a? It turns out that it’s 3a.1.1a.1.1b1. Remember, 3a refers to the first move. We can replace 3a with a new move, named 3a.1.1a. If we want to branch from 3a.1.1a, though, the next state is not 3a.1.1a.1.1a: we’ve already replaced 3a, the first move in the turn. What we want to do is replace the next move in the turn: 3a.1.1a.1.1b. The perhaps-unwanted side effect is that 3a.1.1a.1.1b and 3a.1.1b are siblings: both occur two moves after 3a. A little odd, but necessary.
That about covers the problem of addressing, which is the first problem I’ve addressed. The hard part isn’t generating variation states: the hard part is storing them and finding them by a human-readable address. (I won’t insult you by saying that it’s easy.)
There are other problems, of course: how to present this functionality to the user. I haven’t done that yet. Nor have I done saving and loading of games with variations. In fact, all of this work, which comes to about a week of evenings and 1000 lines of code, has knocked precisely one item off of my v0.4.x to-do list. Fortunately, I think I’ve done at least one of the hard things first. (Loading variations is, admittedly, going to be a huge pain.)
Anyway, you can expect more posts down the line. For now, I have some tests to write.
1. I use that phrasing—’it turns out’—advisedly. Because OpenTafl stores games as a series of board positions, rather than a series of moves, the indexing is all weird. For instance, the state labeled 1a is the starting position, and ‘1a’ refers to the move which exits the starting position. The entire main line of play is addressed in the same way: a state’s address refers to the move which exits that state. You no doubt see the failing here: a variation is a second way to leave the state, and OpenTafl’s not about that kind of ambiguity2. Therefore, so that we can label every move in the game, addresses on variation states have to refer forward, to the move which enters them. The numbering is different between when you branch from 1a (becomes 1a.1.1a) and when you branch from 1a.1.1a (becomes 1a.1.1a.1.1b). Fun3. 2. Here we attribute to principle what is, in reality, just incompetence. 3. In the process of writing this blog post, I’ve discovered and fixed at least three or four inconsistencies in the naming scheme. Rough.
Releasing today is OpenTafl v0.3.3.2b, most likely the final version of OpenTafl in the v0.3.x series. How far we’ve come in the…1 month and a half since these releases kicked off2. After a few false starts, I’ve decided upon this set of features as the final, stable set for v0.3.x.
Beyond the obvious (network play and other associated features), OpenTafl has seen some incidental UI, AI, and framework improvements. Nothing major you haven’t already heard about, so I won’t go into too much depth here. You’ll find that the server login dialog is a little more informative now, and that network games no longer ask for a password when one is not required. You’ll also find (since my last post) that network clients can load saved games, large boards have some extra features (try the ‘info’ command!), network hosts can disallow replay or analysis, and that several network bugs have been fixed. Hit up the README for more information there.
From here out, excepting bugfixes to v0.3.3.2b, my work will be on two new branches. v0.4.x will likely be a long-lived series of releases, since it’ll have both a big-name feature (playable variations) and a long, iterative process of improvements (the AI). Stay tuned for news. I have a pretty good idea of how I want to do playable variations, and a post on that, going from design goals to implementation plans, should be coming soon.
1. Picture me consulting the README. 2. It’s even more dramatic when you consider that, as a public project, OpenTafl is now only about seven months old, and has grown at a rate of nearly 3,000 lines of code per month.
Parvusimperator wrote some about his gear, so it’s only fair that I do, too.
Blackhawk! four-pocket chest rig From everyone’s favorite cheapest decent brand, this chest rig has four large pockets and two small pockets. Each of the large pockets can hold a pair of rifle magazines of your choice, and the small pockets will hold a pistol magazine each.
The design is patterned off of the Chinese Type 81 rig, but isn’t quite identical. In keeping with the Chinese design, the pistol magazine pockets are placed one on each side of the four centered main pockets. All the pockets are secured by velcro. The large pockets are great: they fit the magazines well, and if properly velcroed, secure them to boot. The pistol pockets do what you’d expect: hold magazines. That said, the strong-side pocket is a bit of a pain to get the magazine out of. (See my next item for more on that.)
Anyway, Blackhawk!‘s product seems well-manufactured. They made it out of a properly heavy canvas-y material, which seems to me like it should hold up well under heavy use. (Since I’m only using it for the occasional two-gun match, ruggedness doesn’t matter all that much, but if it comes to a zombie apocalypse, I’m more or less comfortable with it.) At the price I got it for, I certainly can’t complain, especially since it claims it’ll work with AR-15 magazines, too.
Closing out my chest rig thoughts, I had nearly the same experience as parvusimperator: reloads played even less of a role in my time than they did in his. I found myself needing to reload my rifle exactly zero times while running a stage, not counting the stage in which the rifle started unloaded on a table. I could get by with a belt magazine carrier, but I see two obstacles to that: first, nobody makes belt AK mag carriers; second, I like using my ‘duty gear’, as it were, for competition. I’m very unlikely to ever need to use my handgun in a high-pressure non-sporting situation, let alone my rifle chest rig, but my thinking is the same in both cases. I have a limited time budget for practice, in the same way that I have a limited money budget for practice. Why would I spend either on a setup I’ll never use.1
My left front pocket Rather than try to reload from the strong side pistol magazine pocket on the chest rig, I put my second spare mag into my pocket. The pocket was a little too low for complete comfort, but it’s spacious—I could have put a bunch more mags in, if I was trying to carry my full load from the start—and relatively easy to access regardless.
Would I bother with dedicated pistol mag carriers? On the one hand, I could definitely use a few. On the other hand, my current setup is perfectly acceptable, and I don’t know that I would use mag carriers enough outside of competition to merit the expense.
Unlike parvusimperator, I had to dip into my pistol reload stash on basically every stage. The difference between 15 (and my pistol marksmanship) and 18 (and his) is significant enough to tell. I might have liked having another extra magazine,
Company-issue duffel range bag It isn’t a range bag by design—it’s just a small duffel with my company’s logo on the front—but a few airplane trips as my personal carry-on item really tore it up. After the shoulder strap fell off, I demoted it to ‘range bag’. Surprisingly, it handles range duty better, and hasn’t gotten any worse since it switched jobs. Would I like something with more padding, more space, and better internal separation? Yes, but this came in at just the right price2.
My glasses Subpar eye protection, lacking in important qualities like scratch resistance. Ordinarily, your shooting eye protection doesn’t have to be scratch resistant, but I shoot with a wee, short-eye-relief ACOG-style 4x scope, so if my form isn’t perfect, the rifle whacks me in the glasses. My glasses don’t have quite enough anti-scratch strength to take that sort of abuse. I’ll probably get a set of over-glasses eyepro before my next go.
Howard Leight over-the-ear ear protection I prefer earmuff-style earpro to in-ear things, for more attenuation and clearer indication to others whether your earpro is functioning or not. This one was inexpensive, relatively low-profile, padded over the head, and readily available at my local big-box sporting goods retailer. No complaints here.
1. Unless it’s interesting and historical, like the BritKit. 2. Namely, free.
This month, radio gremlins do not replace our show with something straight from 1940, we talk about artillery through the ages in more ways than one, and we report on hitting the dusty competition circuit.
Welcome to Shilovo. It’s July 4th, 1942, and the Wehrmacht has embarked on yet another ambitious offensive: Fall Blau. This time, the plan focuses on the south, pushing from last year’s front (very roughly, a line from Kursk due south to Dnepropetrovsk, then southeast to Rostov, about 800 kilometers in total) to the Baku oilfields and the city of Stalingrad.
It’s only just begun, though, and we concern ourselves with the fighting around Voronezh, and more specifically, a work settlement a bit to the west called Shilovo. (It doesn’t exist anymore—it’s just part of Voronezh.) Shilovo sits on a hill overlooking the Don river, a strategically-important barrier keeping the Nazis out of Voronezh proper. Historically, the Germans took it on July 5th and 6th.
Hopefully, I’ll be able to hold them off a little better than that.
Notice a few features about this map: first, the UI I forgot how to hide. It’s covering the place name for ‘Trushkino’, the town at the bottom center controlled by the Germans. It faces Shilovo across a deep valley. Roads run northwest from Shilovo and northeast from Trushkino, then split to the north and northwest to meet one of the two crossroads objectives. Besides the valley between the two towns, and the hillside south of Shilovo, the map is more or less flat, which presents a problem: I know the Nazis have some armored vehicles, and I don’t have much in the way of anti-tank weaponry. The sum total of my force is as follows: two rifle companies, the battalion machine gun company (ten or so Maxim guns, all told), the battalion mortar company (same deal), and the battalion AT company (armed with anti-tank rifles, which may as well be rocks for all the good they do).
From the Russian side, this is almost entirely a defensive effort, and that’s reflected in my chosen deployment. (We won’t talk about my first mission in this campaign, a defense to the northwest. It didn’t go well.) One rifle company, under Homenko, is deployed at the northern crossroads, reinforced by most of Beda’s platoon. Drobotov’s platoon holds the central crossroads, while Churginov’s platoon serves as a reserve between the two. Bits and pieces of the machine gun company and the anti-tank company are detached to strengthen the two crossroads strongpoints.
The remainder of Beda’s platoon, along with the battalion mortars and the bulk of the machine guns, are deployed on the forward slope on the western approach to Shilovo, commanding the valley. With good, overlapping fields of fire, and tons of ammunition to boot, I suspect the machine guns will serve to hold the valley approach to Shilovo without issue. I’m more concerned about the central crossroads. If the Germans bring tanks down the west road, I’ll have a bad time of things. Hopefully, the northern crossroads strongpoint will be sufficiently distracting.
Anyway. Let’s get this show on the road. I had hoped to provide some extra screenshots here beyond the few I took during the battle, but alas, my VLC screenshot button isn’t working correctly, so you’ll just have to rely on your war correspondent, me.
The Germans begin their attack with a push, oddly enough, across the valley. The machine guns deliver a murderous hail of fire into the advancing Wehrmacht troops, and in large part, the advance stalls about halfway to my line. German forces will rally and push up the hill somewhat, but never in any organized manner, and never any closer than about one hundred meters to the guns.
Gunners on the northeastern outskirts of Shilovo engage German forces in the trees near the Trushkino road.
The northern crossroads, as I thought might be the case, turn out to be more interesting. It takes the Germans about ten minutes longer to make it down the road toward the strongpoint, but they arrive in greater force, and I have fewer heavy weapons to spare. It quickly becomes clear that the main German advance is coming from the west along the main road, so I shift some of the defenders facing north—a second machine gun team, and one of Beda’s squads—to meet the threat.
The fire on my position intensifies. The Germans clearly want this crossroads. Mortar fire begins to land in town, and the piddly 50mm mortars attached to each of my companies can’t even begin to fire in reply. They stick to shooting at the oncoming Germans, which is admittedly more scary than effective. (Your average 50mm mortar bomb has about 100 grams of explosive, which is less than some hand grenades of the time.)
The situation worsens about 20 minutes into the mission. A halftrack comes down the road, and while its mounted machine gun is keeping my anti-tank gunners’ heads firmly below trench level, a pair of Panzer IIs roll up the road. This is no good. Time to bring in the reserves.
A machine gun team shoots past Russian trenches (at frame left) toward advancing German infantry, while a Panzer approaches from the right.
One of the anti-tank gunners manages to get a shot off at the halftrack, which is enough to force its crew to bail out. By now, though, the Panzers have backed off, and are now working their way around to the north, where my defenses are lighter. One of them pushes into the town, about fifty yards behind the camera above, and begins shooting up my poor defenders. Fortunately, between the carnage west of Shilovo and the reserves arriving and bulking up the line south of the crossroads, the Germans realize they can’t hope to break through without further reinforcement. They call for a cease fire, and I gladly accept.
The casualty ratio favors me, as you might expect from a victory in a dug-in, defensive battle. I started with 400 men, of which about 250 were front-line combat troops, and lost 50, including a few machine guns lost and a few abandoned. (The abandoned ones will be recovered.) The Germans lost 150 out of 360, including one halftrack. I put some fire on both tanks, but neither appear to have been greatly inconvenienced by it, and undoubtedly, they’ll show up again.
Having survived this battle, I only had one more to play on the first turn, and it played out very similarly—the battle played out over Shilovo again, except shifted one grid square south. The same deployment, with machine guns covering open ground, served me well, and I’m into the second turn of the campaign now. I was able to bring some artillery up all along the line, along with anti-tank guns and air spotters. I expect the next few battles will feature much improved fireworks.
A new version of OpenTafl is out. Happily, this one doesn’t break network compatibility! As usual, the README has full details, but here are the highlights.
First off, performance improvements! The micro-optimizations I wrote about are now in the release. This brings OpenTafl’s speed up to the standard set by v0.2.5.3b. You may also notice enhanced responsiveness from the UI, which comes from updates to the Lanterna UI library.
Speaking of which, updates to said library have also resolved issues with OpenTafl drawing in native terminals. Use the –fallback switch to run OpenTafl in pure ANSI terminal mode. Handy if you’re on a server or something. Changes in Lanterna also required a little bit of rewriting on the Swing front; the upshot is that font size is now configurable.
Finally, I took care of a few large-board issues: the row indices now print correctly for boards larger than 9×9. In the same vein, alea evangelii (19×19 tafl) is now available, and I can feel a 19×19 tafl theory post coming soon, I think.
I went into Zootopia with moderate expectations—I had heard good things, but even as a fan of animated movies, I wasn’t expecting anything to boggle the mind. Ultimately, I was still expecting a kids movie with crossover appeal.
This is not what Disney delivered. Zootopia starts out a cheerful-seeming puff piece; by the end, it has taken on an almost noirish feel, telling a pitch-perfect buddy cop story in an exquisitely-detailed world. I can’t say much more without giving away plot points, and the plot is so well-crafted I would feel guilty doing so, but really. If you’re skeptical, fear not: it is not what the previews suggest it is. It’s much better. Go see it. I have not yet heard anyone credible claim to be disappointed.
Done? Cool. I’m going to employ a piece of sorcery most arcane known as ‘the fold’ to hide possible spoilers from casual readers. (Very minor—I’m extremely allergic to spoilers. If you don’t mind non-specific remarks about the flow of the plot through the three acts, you’ll be fine.) Join me on the other side.
Tonight, OpenTafl saw its first micro-optimization!
Let me start from the beginning, though. OpenTafl has a static Coord type, which holds precalculated information about coordinates: what their index is, where they are on the board, and so on. Before network mode, OpenTafl updated the Coord type at the start of each game to correspond to the board size for the selected rules variation.
Astute readers may have noticed the problem. On the server, multiple games may be ongoing, on boards of different sizes. The Coord object should therefore have all the information required for any size of board. The network mode patches included a rewrite of Coord to hold all the information at once, indexed in maps by board size. This solved the problem, but yielded about a performance hit of about ten to fifteen percent. (Obviously, the Coord code paths come up a lot.)
At first, I wasn’t going to worry about it. Then, I had a little downtime this afternoon and decided, “Well, I’m not going to get anything else done right now.” Firing up the old profiler, I found a hotspot to work on.
When exploring the game tree, OpenTafl caches information about how pieces can move. (Calculating it out every time is computationally expensive, or at least more computationally expensive than can be justified doing it every time.) Clearing this cache involves zeroing an array. The usual way to do this is to loop over the array and set everything to zero. (Whether you choose a library function or write it by hand, this is usually what happens.) Unfortunately, that ‘reset’ function, according to the profiler, took longer on aggregate than any other single operation, including such expensive calculations as shieldwall detection and surrounding victories. This would not do.
The solution? Well, although Java’s library methods for array filling do not use native code memory copying, Java’s library method for copying one array to another does. The titular micro-optimization, therefore, was to set the first slot of the array to the desired value, then copy that to the second, then copy those two to the second two, then copy those four to the next four, and so on until the array is fully filled. Since this works directly on system memory, it turns out to be faster.
How much faster? To answer that question, I wrote a little benchmark function for OpenTafl, which runs a 30-second brandub search, a 30-second tablut 9×9 search, a 60-second Copenhagen search, and a 60-second Tablut 15×15 search, which verified the 10-15% slowdown from pre-network to post-network. Fortunately, the move cache optimization yielded a speedup of about 15%, bringing us right back to where we were before. Et voila.
