Tag Archives: coding

OpenTafl v0.4.6.2b released

OpenTafl has seen some major development work for the first time in a while, culminating in the recent release of v0.4.6.2b.

This version adds some major features which have been on my to-do list for some time. First, the in-game and replay board views now support keyboard input, a major usability enhancement. No longer will mistaken command entries torpedo your games!

That feature, however, was merely a happy piece of good fortune, falling out of the true headline feature for the v0.4.6.x releases: a variant editor. That’s right. OpenTafl is now the best tool available for designing tafl rules, bar none. Not only can you individually tweak every rule described in the OpenTafl notation specification, you can also edit the board layout to look any way you like.

If you’re interested in playing a few games with the new UI or experimenting with rules variants all your own, you can, as always, get the latest version from the OpenTafl website. I haven’t promoted v0.4.6.x to the stable release yet, but I expect to do so soon.

With these features done, I turn my attention next to a few network-centric things for v0.5.x. OpenTafl’s network play server has not, to date, seen much use; now that PlayTaflOnline.com is getting close to its new architecture, I hope to write a PlayTaflOnline front end for OpenTafl, so you can use OpenTafl to play games at PlayTaflOnline, with all the rich support for replays, commentary, and analysis from OpenTafl. OpenTafl’s network server mode and self-contained network play will continue to be a supported mechanism for remote games, but won’t see new features. v0.5.x will also contain an automatic updater, to simplify the end-user updating process.

Looking further into the future, I’m running out of OpenTafl features I want to do. With luck, 2017 will see a v1.0 release.

How-To: Two USB Mics, One Computer, JACK, and Audacity

The Crossbox Podcast is going upmarket: I now have two USB microphones, and for the March episode, parvusimperator and I will each have one directly in front of us. This is a wonderful advance for audio quality, but it does pose some problems:

  1. Audacity, our usual recording tool of choice (and probably yours, if you ended up here), only supports recording from one source at once.
  2. Though other tools support recording from multiple sources, the minor variations in internal clocks between two USB microphones mean that each microphone has a sample rate which varies in a slightly different fashion, and that longer recordings will therefore be out of sync.

Modern Linux, fortunately, can help us out here. We have need of several components. First, obviously, we need two microphones. I have a Blue Snowball and a CAD Audio U37, with which I’ve tested this procedure1. Second, we need a computer with at least two USB ports. Third, we need the snd-aloop kernel module. (If your Linux has ALSA, you probably already have this.) Fourth, we need JACK, the Linux low-latency audio server. Fifth, we need the QJackCtl program.

Before I describe what we’re going to do, I ought to provide a quick refresher in Linux audio infrastructure. If you use Ubuntu or Mint, or most other common distributions, there are two layers to your system’s audio. Closest to the hardware is ALSA, the kernel-level Advanced Linux Sound Architecture. It handles interacting with your sound card, and provides an API to user-level applications. The most common user-level application is the PulseAudio server, which provides many of the capabilities you think of as part of your sound system, such as volume per application and the ‘sound’ control panel in your Linux flavor of choice. (Unless you don’t use Pulse.)

JACK is a low-latency audio server; that is, a user-level application in the same vein as Pulse. It has fewer easily accessible features, but allows us to do some fancy footwork in how we connect inputs to outputs.

Now that you have the background, here’s what we’re going to do to connect two mono USB microphones to one computer, then send them to one two-channel ALSA device, then record in Audacity. These instructions should work for any modern Linux flavor. Depending on the particulars of your system, you may even be able to set up real-time monitoring.

  1. Create an ALSA loopback device using the snd-aloop kernel module.
  2. Install JACK.
  3. Build QJackCtl, a little application used to control JACK. (This step is optional, but makes things much easier; I won’t be providing the how-to for using the command line.)
  4. Use JACK’s alsa_in and alsa_out clients to give JACK access to the microphones and the loopback device.
  5. Use QJackCtl to connect the devices so that we can record both microphones at once.

We’ll also look at some extended and improved uses, including some potential fixes for real-time monitoring.

Create an ALSA loopback device
The ALSA loopback device is a feature of the kernel module snd-aloop. All you need to do is # modprobe snd-aloop and you’re good to go. Verify that the loopback device is present by checking for it in the output of aplay -l.

The loopback device is very straightforward: any input to a certain loopback device will be available as output on a different loopback device. ALSA devices are named by a type string (such as ‘hw’), followed by a colon, then a name or number identifying the audio card, a comma, and the device number inside the card. Optionally, there may be another comma and a subdevice number. Let’s take a look at some examples.

  • hw:1,0: a hardware device, card ID 1, device ID 0.
  • hw:Loopback,1,3: a hardware device, card name Loopback, device ID 1, sub-device ID 3.

For the loopback device, anything input to device ID 1 and a given sub-device ID n (that is, hw:Loopback,1,n) will be available as output on hw:Loopback,0,n, and vice versa. This will be important later.

Install JACK
You should be able to find JACK in your package manager2, along with Jack Rack. In Ubuntu and derivatives, the package names are ‘jackd’ and ‘jack-rack’.

Build QJackCtl
QJackCtl is a Qt5 application. To build it, you’ll need qt5 and some assorted libraries and header packages. I run Linux Mint; this is the set I had to install.

  • qt5-qmake
  • qt5-default
  • qtbase5-dev
  • libjack-jack2-dev
  • libqt5x11extras5-dev
  • qttools5-dev-tools

Once you’ve installed those, unpack the QJackCtl archive in its own directory, and run ./configure and make in that directory. The output to configure will tell you if you can’t continue, and should offer some guidance on what you’re missing. Once you’ve successfully built the application, run make install as root.

Run QJackCtl
Run qjackctl from a terminal. We should take note of one feature in particular in the status window. With JACK stopped, you’ll notice a green zero, followed by another zero in parentheses, beneath the ‘Stopped’ label. This is the XRUN counter, which counts up whenever JACK doesn’t have time to finish a task inside its latency settings.

Speaking of, open the settings window. Front and center, you’ll see three settings: sample rate, frames per period, and periods per buffer. Taken together, these settings control latency. You’ll probably want to set the sample rate to 48000, 48 kHz; that’s the standard for USB microphones, and saves some CPU time. For the moment, set frames per period to 4096 and periods per buffer to 2. These are safe settings, in my experience. We’ll start there and (maybe) reduce latency later.

Close the settings window and press the ‘Start’ button in QJackCtl. After a moment or two, JACK will start. Verify that it’s running without generating any XRUN notifications. If it is generating XRUNs, skip down to here and try some of the latency-reduction tips, then come back when you’re done.

Use JACK’s alsa_in and alsa_out clients to let JACK access devices
Now we begin to put everything together. As you’ll recall, our goal is to take our two (mono) microphones and link them together into one ALSA device. We’ll first use the alsa_in client to create JACK devices for our two microphones. The alsa_in client solves problem #2 for us: its whole raison d’être is to allow us to use several ALSA devices at once which may differ in sample rate or clock drift.

Now, it’s time to plug in your microphones. Do so, and run arecord -l. You’ll see output something like this.

$ arecord -l
**** List of CAPTURE Hardware Devices ****
card 0: PCH [HDA Intel PCH], device 0: ALC295 Analog [ALC295 Analog]
  Subdevices: 1/1
  Subdevice #0: subdevice #0
card 1: Audio [CAD Audio], device 0: USB Audio [USB Audio]
  Subdevices: 1/1
  Subdevice #0: subdevice #0
card 2: Snowball [Blue Snowball], device 0: USB Audio [USB Audio]
  Subdevices: 0/1
  Subdevice #0: subdevice #0

This lists all the currently available capture hardware devices plugged into your system. Besides the first entry, the integrated microphone on my laptop, I have hw:1 or hw:Audio, the CAD Audio U37, and hw:2 or hw:Snowball, the Blue Snowball.

Next, set up alsa_in clients so JACK can access the microphones.

$ alsa_in -j snow -d hw:Snowball -c 1 -p 4096 -n 2 &
$ alsa_in -j cad -d hw:Audio -c 1 -p 4096 -n 2 &

Let’s go through the options. -j defines the label JACK will use for the microphone; make it something descriptive. -d declares which ALSA device JACK will open. -c declares the number of channels JACK will attempt to open.

On to the last two options: like the JACK settings above, -p defines the number of frames per period, and -n defines the number of periods per buffer. The documentation for alsa_in suggests that the total frames per buffer (frames per period multiplied by period) should be greater than or equal to JACK’s total frames per buffer.

Next, set up an alsa_out client for the ALSA loopback device.

$ alsa_out -j loop -d hw:Loopback,1,0 -p 4096 -n 2 &

The arguments here are the same as the arguments above.

Use QJackCtl to hook everything up
Now, we’re almost done. Go back to QJackCtl and open the Connect window. You should see a list of inputs on the left and a list of outputs on the right. Your inputs should include your two microphones, with the names you provided in your -j arguments. Your outputs should include system, which is linked to your system’s audio output, and an output named ‘loop’, the ALSA loopback device.

Assuming you have mono microphones, what you want to do is this: expand a microphone and highlight its input channel. Then, highlight the system output and hit ‘connect’ at the bottom of the window. This will connect the input channel to the left and right channels of your system audio output. At this point, you should be able to hear the microphone input through your system audio output. (I would recommend headphones.) The latency will be very high, but we’ll see about correcting that later.

If the audio output contains unexpected buzzing or clicking, your computer can’t keep up with the latency settings you have selected3. Skip ahead to the latency reduction settings. That said, your system should be able to keep up with the 4096/2 settings; they’re something of a worst-case scenario.

If the audio output is good, disconnect the microphones from the system output. Then, connect one microphone’s input to loop’s left channel, and one microphone input to loop’s right channel. Open Audacity, set the recording input to Loopback,04, and start recording. You should see audio from your microphones coming in on the left and right channel. Once you’re finished recording, you can split the stereo track into two mono tracks for individual editing, and there you have it: two USB microphones plugged directly into your computer, recording as one.

Recording more than two channels
Using Jack Rack, you can record as many channels as your hardware allows. Open Jack Rack, and using the ‘Channels’ menu item under the ‘Rack’ menu, set the number of channels you would like to record. In QJackCtl’s connections window, there will be a jackrack device with the appropriate number of I/O channels.

In Audacity, you can change the recording mode from ALSA to JACK, then select the jackrack device, setting the channel count to the correct number. When you record, you will record that many channels.

Jack Rack is, as the name suggests, an effects rack. You can download LADSPA plugins to apply various effects to your inputs and outputs. An amplifier, for instance, would give you volume control per input, which is useful in multi-microphone situations.

Reduce frames per period
If you’re satisfied with recording-only, or if you have some other means of monitoring, you can stop reading here. If, like me, you want to monitoring through your new Linux digital audio workstation, read on.

The first step is to start reducing the frames per period setting in JACK, and correspondingly in the alsa_in and alsa_out devices. If you can get down to 512 frames/2 periods without JACK xruns, you can probably call it a day. Note that Linux is a little casual with IRQ assignments and other latency-impacting decisions; what works one day may not work the next.

You can also try using lower frames per period settings, and higher periods per buffer settings, like 256/3 or 512/3. This may work for you, but didn’t work for me.

If you come to an acceptable monitoring latency, congratulations! You’re finished. If not, read on.


Fixing latency problems
Below, I provide three potential latency-reducing tactics, in increasing order of difficulty. At the bottom of the article, just above the footnotes, is an all-in-one solution which sacrifices a bit of convenience for a great deal of ease of use. My recommendation, if you’ve made it this far, is that you skip the three potential tactics and go to the one which definitely will work.

Further latency reduction: run JACK in realtime mode
If JACK is installed, run sudo dpkg-reconfigure -p high jackd (or dpkg-reconfigure as root).

Verify that this created or updated the /etc/security/limits.d/audio.conf file. It should have lines granting the audio group (@audio) permission to run programs at real-time priorities up to 95, and lock an unlimited amount of memory. Reboot, set JACK to use realtime mode in QJackCtl’s setup panel, and start JACK. Try reducing your latency settings again, and see what happens.

Further latency reduction: enable threaded IRQs
Threaded IRQs are a Linux kernel feature which help deliver interrupt requests5 more quickly. This may help reduce latency. Open /etc/default/grub. Inside the quotation marks at the end of the line which starts with GRUB_CMDLINE_LINUX_DEFAULT, add threadirqs, and reboot.

Further latency reduction: run a low-latency or real-time kernel
If none of these help, you might try running a low-latency kernel. You can attempt to compile and use low-latency or real-time kernels; the Ubuntu Studio project provides them, and there are packages available for Debian. If you’ve come this far, though, I’d recommend the…

All-of-the-above solution: run an audio-focused Linux distribution
AV Linux is a Linux distribution focused on audio and video production. As such, it already employs the three tactics given above. It also includes a large amount of preinstalled, free, open-source AV software. It isn’t a daily driver distribution; rather, its foremost purpose is to be an audio or video workstation. It worked perfectly for me out of the box, and met my real-time monitoring and audio playback requirements for The Crossbox Podcast6. I recommend it wholeheartedly.

Given that my laptop is not primarily a podcast production device, I decided to carve a little 32gb partition out of the space at the end of my Windows partition, and installed AV Linux there. It records to my main Linux data partition instead of to the partition to which it is installed, and seems perfectly happy with this arrangement.

So am I. Anyway, thanks for reading. I hope it helped!


  1. Two identical microphones actually makes it slightly (though not insurmountably) harder, since they end up with the same ALSA name. 
  2. If you don’t have a package manager, you ought to be smart enough to know where to look. 
  3. This is most likely not because of your CPU, but rather because your Linux kernel does not have sufficient low-latency features to manage moving audio at the speeds we need it to move. 
  4. Remember, since we’re outputting to Loopback,1, that audio will be available for recording on Loopback,0. 
  5. Interrupt requests, or IRQs, are mechanisms by which hardware can interrupt a running program to run a special program known as an interrupt handler. Hardware sends interrupt requests to indicate that something has happened. Running them on independent threads improves the throughput, since more than one can happen at once, and, since they can be run on CPU cores not currently occupied, they interrupt other programs (like JACK) less frequently. 
  6. Expect us to hit our news countdown time cues a little more exactly, going forward. 

OpenTafl AI roundup: bugs and features

This post will cover OpenTafl AI changes since the last post I wrote on the topic, further back in the v0.4.x releases. First, bugs!

Let’s do some quick recap. OpenTafl’s AI is a standard, deterministic1 tree-searching AI, using iterative deepening. That means that OpenTafl searches the whole tree2 to depth 1, then to depth 2, then depth 3, and so on, until it no longer has enough time to finish a full search3.

You may have noticed, if you’ve used OpenTafl, that searching to depth n+1 takes a longer than searching to depth n, and that it’s altogether possible that the process above might leave OpenTafl with a lot of time left over. I did not fail to notice this, and I implemented a couple of additional searches (extension searches, as they’re known) to help fill in this time.

The first, I refer to as continuation search. Continuation search takes the existing tree and starts a new search at the root node, using the work already done and searching to depth n+1. Obviously, continuation search doesn’t expect to finish that search, but it will reach some new nodes and provide us some new information. After continuation search, OpenTafl does what I call a horizon search: it finds the leaf nodes corresponding to the current best-known children of the root node, then runs normal searches starting with the leaf nodes, to verify that there aren’t terrible consequences to a certain move lurking just behind the search horizon.

These are fairly easy concepts to understand, my poor explanations notwithstanding. The bugs I referred to in the title are more insidious. They come down to a much more complicated concept: what conditions must the children of a node meet for that node’s evaluation to be valid?

In the iterative deepening phase of the search, the answer doesn’t matter. Remember, OpenTafl discards any tree it doesn’t finish. When we’re doing extension searches, though, we don’t have that luxury. OpenTafl must be able to discern when a certain node has not been fully searched. I added a flag value to the search to note that a certain node has been left intentionally unvalued, which gets set whenever we have to abandon a search because we’ve run out of time. If a node did not exist in the tree prior to the extension search, and it has unvalued children, then it is also unvalued. If a node did exist in the tree prior to its extension search and it has unvalued children, this is okay! We ignore the unvalued children and use the information we’ve gained4. If an unvalued node is left in the tree after those steps, we ignore its value. Any unvalued node is misleading, and we should avoid using its value when deciding how to play.

This issue led to poor play, as both horizon and continuation search had a chance to introduce bad data into the tree. I finally tracked it down and fixed it in v0.4.4.6b.

After that, I came across another few bugs, lesser in severity but still quite bad for OpenTafl’s play: when evaluating a draw position for the attackers, OpenTafl would incorrectly view it as more defender-favorable than it should have been5. OpenTafl also had some trouble with repetitions, incorrectly failing to increment the repetitions table in some search situations. That’s one of the more important gains over v0.4.4.7b—v0.4.5.0b is absolutely incisive in playing out repetitions, as some of the players at playtaflonline.com discovered after the update.

Finally, a few minor time usage bugs are no longer present, although there are some headscratchers where the AI seems to lose half a second or so to some task I cannot locate, and some task it does not count when doing its time use accounting.

That about wraps up bugs. Features, as usual, are more fun.

First, OpenTafl now is willing to play for a draw in rare circumstances. If its evaluation tilts overwhelmingly toward the other side, and it sees a draw in its search tree, it evaluates the draw poorly, but better than a loss.

That depends on the second feature, which is an improved evaluation function. Rather than guess, I decided to be scientific about it: I built four OpenTafl variants, each with a certain evaluation coefficient raised above the rest. Those variants played each other in a battle royale, and based on the outcome, I picked new coefficients. They differ by size; 7×7 boards consider material more heavily, while larger boards prefer to play positionally6.

Positional play comes from the last and most important feature: piece square tables. Credit for the idea goes to Andreas Persson (on Twitter @apgamesdev), who linked me to the chessprogramming wiki article, and also provided a first pass at the tables.

I should back up a bit first, though. Piece square tables are descriptively-named tables which assign a value to having a certain piece type on a certain space. For instance, the space diagonally adjacent to a corner space in a corner-escape game is very important for the besiegers. That space gets a high positive coefficient. On the other hand, the spaces directly adjacent to the corners are quite bad for the attackers, and get a moderately large negative coefficient. OpenTafl’s evaluator handles the exact values.

The benefits of this approach are manifold: not only does OpenTafl know when the opponent is building a good shape, it now has a sense for position in a global sense. (It previously had some sense of position relative to other pieces, but that was not sufficient.) Because of this, it is much better now at picking moves which serve more than one purpose. If it can strengthen its shape by making a capture, it’ll do so. If it can weaken its opponent’s shape, so much the better. The code which generates the piece square tables can be found here7.

The outcome is most pleasing. I can no longer easily beat OpenTafl on 11×11 corner escape boards, and games in that family are presently the most popular in online play. Equal-time matches are all but a lost cause, and I have to engage my brain in a way I never did before if I allow myself more thinking time. Now, I am not all that good a player, and those who are better than me still handle OpenTafl pretty roughly, but it now plays at a low-intermediate level. Given that it barely even existed twelve months ago, I’d say that’s good progress.


  1. Mostly. 
  2. Kind of. 
  3. More or less. For being mostly deterministic, AI stuff is remarkably fuzzy. On an unrelated note, look! We have new footnotes, with links and everything! 
  4. You can construct a game tree where this assumption—that not searching all of the outcomes when exploring an already-valued node is acceptable—causes trouble, but the fault for that lies more with the evaluation function than with the search. In such cases, the evaluation function must be so incorrect as to evaluate a node which leads to a loss just over the horizon as better than a node which does not lead to an imminent loss to a slightly deeper depth. They are quite rare, though, and I haven’t come across one yet in testing. 
  5. It was supposed to be a plus sign, but it was a minus sign instead. Oops. 
  6. On the to-do list is changing coefficients over the course of a game—brandub is more or less an endgame study, and at some point, the evaluator should prefer material over position in endgames even on larger boards. 
  7. I chose to generate the tables because it’s easier to maintain and update. Work for corner-escape 11×11 boards generalizes to most corner escape variants; the same is true for edges. The only boards which really, truly take special cases are 7×7, since the corners are such a vast majority of the board, and moves which might be considered neutral or iffy on larger boards ought to be given a chance—there aren’t many options in the first place. 

2016 Tafl Efforts: Results and Roundup

First off: the inaugural OpenTafl Computer Tafl Open has come to a close. It was a bit of an anticlimax, I must admit, but fun times nevertheless.

To recap, only one entry (J.A.R.L) made it in on time. On January 2nd, I had the AIs run their matches, and it was all over inside of 20 minutes, with a bit of technical difficulty time to boot. You can find the game records here.

To move one layer deeper into the recap, both AIs won one game each out of the match. J.A.R.L won in 22 moves, OpenTafl won in 18, giving the victory to OpenTafl. Disappointingly for me, OpenTafl played quite poorly in its stint as the attackers, allowing J.A.R.L to quickly set up a strong structure funneling its king to the bottom right of the board. Disappointingly for Jono, J.A.R.L seemed to go off the rails when it played the attacking side, leaving open ranks and files and leaving a certain victory for OpenTafl. Deeper analysis is coming, although, not being a great player myself, I can’t offer too much insight. (Especially given that neither AI played especially well.)

I do expect that, when Jono finishes fixing J.A.R.L, it’ll be stronger than OpenTafl is today. He intends on making its source code available in the coming year, as a starting point for further AI development. (If feasible, I hope to steal his distance-to-the-corner evaluation.)

There will be a 2017 OpenTafl Computer Tafl Open, with the same rules and schedule. I’ll be creating a page for it soon.

Next: progress on OpenTafl itself. It’s difficult to overstate how much has happened in the past year. Last January, OpenTafl was a very simple command-line program with none of the persistent-screen features it has today; it had no support for external AIs, no multiplayer, no notation or saved games, and a comparatively rudimentary built-in AI.

The first major change of the year was switching to Lanterna, and that enabled many of the following ones. Lanterna, the terminal graphics framework OpenTafl uses to render to the screen, allows for tons of fancy features the original, not-really-solution did not. Menus, for one. For another, a UI which makes sense for the complicated application OpenTafl was destined to become. Although it’s the easiest thing to overlook in this list of features, it’s the most foundational. Very few of the remaining items could have happened without it.

Next up: external AI support. In the early days, I only planned for OpenTafl to be a fun little toy. At the end of that plan, it might have been something I could use to play my weekly (… well, kind of) tafl game without having to deal with a web interface. (For what it’s worth, Tuireann’s playtaflonline.com renders that goal obsolete, unless you really like OpenTafl.)

Later on, as I got into work on OpenTafl’s built-in AI, I realized what an amazing object of mathematical interest it is, and that it has not, to date, seen anything like the kind of study it richly deserves. As such, I decided I wanted OpenTafl to be a host for that sort of study. Much of what we know about chess, go, and other historical abstract strategy games comes from the enormous corpus of games played. That corpus does not yet exist for tafl games, the amazing efforts of people like Aage Nielsen and Tuireann notwithstanding. The quickest way to develop a good corpus is to play lots of games between good AIs. Good AIs are hard to come by if every AI author also needs to build a UI and a host.

So, OpenTafl fills the void: by implementing OpenTafl’s straightforward engine protocol, AI authors suddenly gain access to a broad spectrum of opponents. To start with, they can play their AI against all other AIs implementing the protocol, any interested human with a copy of OpenTafl, and possibly even the tafl mavens at playtaflonline.com. Not only that, but the AI selfplay mode allows AI authors to verify progress, a critical part of the development process.

Multiplayer was an obvious extension, although it hasn’t seen a great deal of use. (There are, admittedly, better systems out there.) It proved to be relatively straightforward, and although there are some features I’d like to work out eventually (such as tournaments, a more permanent database, and a system for client-side latency tracking to allow for client-side correction of the received server clock stats), I’m happy with it as it stands.

OpenTafl is also the first tafl tool to define a full specification for tafl notation, and the first to fully implement its specification. The Java files which parse OpenTafl notation to OpenTafl objects, and which turn OpenTafl objects into OpenTafl notation, are in the public domain, free for anyone to modify for their own AI projects, another major benefit.

In defining OpenTafl notation, I wanted to do two things: first, to craft a notation which is easily human-readable, in the tradition of chess notation; and second, to remain interoperable with previous tafl notation efforts, such as Damian Walker’s. The latter goal was trivial; OpenTafl notation is a superset of other tafl notations. The former goal was a little more difficult, and the rules notation is notably rather hard to sight-read unless you’re very familiar with it, but on balance, I think the notations people care about most—moves and games—are quite clear.

Having defined a notation and written code to parse and generate it, I was a hop, skip, and jump away from saved games. Shortly after, I moved on to replays and commentaries. Once again a first: OpenTafl is the first tool which can be used to view and edit annotations on game replays. Puzzles were another obvious addition. In 2017, I hope to release puzzles on a more or less regular basis.

Last and the opposite of least, the AI. Until the tournament revealed that J.A.R.L is on par with or better than OpenTafl, OpenTafl was the strongest tafl-playing program in existence. I’ve written lengthy posts on the AI in the past, and hope to come up with another one soon, talking about changes in v0.4.5.0b, which greatly improved OpenTafl’s play on large boards.

Finally, plans. 2017 will likely be a maintenance year for OpenTafl, since other personal projects demand my time. I may tackle some of the multiplayer features, and I’ll probably dabble in AI improvements, but 2017 will not resemble 2016 in pace of work. I hope to run a 2017 tafl tournament, especially since the engine protocol is now stable, along with OpenTafl itself. I may also explore creating a PPA for OpenTafl.

Anyway, there you have it: 2016 in review. Look for the AI post in the coming weeks.

Random Carrier Battles: what’s in the prototype, then?

Yesterday, we spoke briefly of what’s getting left out of Random Carrier Battles’ first playable prototype. Today, we’ll cover the happier side of that story: what’s in!

UI stuff
I have some informational interface tasks to take care of, to allow players to view task force members and elements of air groups. I figure to stick this on the left side of the main UI.

Some aircraft design improvements
I believe I’ll need to make some tweaks to aircraft and escort design, to specify quality of armament: the early use of the TBF Avenger was hampered by the poor quality of the Mark 13 air-launched torpedo, and I can’t capture that in the system as is. Similarly, British battlecruisers, German pocket battleships, and Yamato aren’t well-captured by the system as is. (Battlecruisers, in this framing, would be heavy cruisers with good guns; Scharnhorst would be battleships with poor guns, and Yamato would be a battleship with good guns.) Although surface combat is out of scope for the initial prototype, I want to have enough data to do a passable job at it when I come to it.

I may also have to make radios a feature of airplane design, so that types with historically good radios can communicate better than types with historically poor radios.

Aircraft handling: repair, fueling, arming, launching, recovery
Aircraft handling is a big focus of Random Carrier Battles: more than previous games in the carriers-at-war genre, I want to get down into the weeds. I want to track aircraft status to a fine-grained level of detail, down to how far along arming and fueling have progressed, or how warmed-up the engine is. On deck, I don’t think I plan to track exactly where planes are spotted, but I may do some tracking of takeoff run available—this would penalize light aircraft carriers with large air wings by preventing them from launching everything in one go, which is, in my view, a feature.

In terms of discrete development tasks, I’ll have to figure out how to turn a designed air group into an air group instance in the game world, build systems to hold air operations status and control transitions between air operations states, and build UI to control it all.

This feature will also lay the groundwork for land-based airfields, as well as seaplane tenders and seaplane-carrying cruisers.

Air combat!
Making this one heading is perhaps a bit ambitious on my part, but there you are. Air combat has a bevy of subordinate features, including representing armaments (to give damage) and ship and aircraft systems (to take damage), a planner for missions, and unit combat behavior AI.

Systems and armaments are the easiest of the bunch; they merely involve defining a set of systems for each class of asset, along with a set of armaments generated from the asset’s statistics and arming status.

The mission planner is a complicated feature, and one which I hope will be industry-leading: a central clearinghouse where admirals can view all missions currently planned or in progress, create new missions, cancel unlaunched missions, and eventually, handle every air operation in the task force. For now, it may fall to players to prepare the aircraft assigned to missions on their own initiative, depending on how the aircraft handling features shake out.

Finally, combat behavior AI: this is by far the biggest feature under this heading, and the hardest to handle. It includes automatic marshaling of air groups (players won’t have direct control over aircraft in flight), CAP behavior, scout plane behavior, strike planes’ flights to their targets, and attack behavior for dive bombers and torpedo bombers. Ships will also have to maneuver under direct attack (that is, to avoid incoming torpedoes, and to throw off dive bombers’ aim).

Initial spotting and scouting
Spotting and scouting in their fullness will require a lot of work, so I’m going to build a simpler system to start with. Simply put, you can see everything on your side, and anything within horizon range of your ships and planes.

Submarines will come later.

That’s that! I hope you find these plans as exciting as I do. I hope to get the demo to a state where I can take some usable screenshots and videos and submit to Steam Greenlight, at which point I’ll be hitting you up for upvotes.

Random Carrier Battles: the road to a playable prototype

Good afternoon, and happy Thanksgiving! While sitting here watching the turkey and the giblet broth, I had some time to work out a little roadmap for taking Random Carrier Battles from its current state, barely above proof of concept that the Godot engine is suitable for this purpose, to a playable prototype (if one that doesn’t capture my full vision).

So, to get the ugly out of the way first, let’s talk about what I’m leaving (for now) on the cutting room floor.

Wind and weather
Though they are crucial parts of aviation, they’re incredibly complicated, and I want to do them right the first time, rather than hacking something together now. With modern processors and multi-threading, I can push weather simulation into the background and only update every few in-game minutes, which leaves me lots of time to try interesting simulation techniques. ‘Interesting’, as I said, is a synonym for ‘hard’, and so I won’t be exploring these yet.

Land-based air
It may turn out that the mechanics of land-based air—launching and recovery—is a freebie based on doing carrier-based air. If it isn’t, though, I’ll tackle it later, along with design for land-based types like multi-engine bombers and flying boats.

Full visibility and spotting system
My plan for Random Carrier Battles is to attempt to capture just how blind carrier admirals were a lot of the time. Enemy positions will only be known by spotting reports, and allied air positions will only be known with full precision when they can be seen from friendly task forces. All of that will require a detailed system for spotting and visibility, and a system for displaying and archiving spotting reports. It’s less straightforward than it sounds, since the AI (when that arrives) will need access to that information for its fleet. Speaking of…

Artificial intelligence
I may provide some sort of rudimentary AI, but I may also leave it more or less entirely to scripting, or give the computer perfect knowledge. Don’t expect anything amazing, at any rate.

So, what does that leave to do? Nothing less than the core of the game. Come back tomorrow or Saturday for details!

Random Carrier Battles: kinematics and scale

I spent some time the other day playing the old-school DOS version of the current state of the art in carrier air warfare simulations, SSG’s 1992 classic appropriately entitled titled Carriers at War. As far as DOS-era wargames go, it’s pretty good—it doesn’t bother you with too many details, and it (largely) lets you focus on the grander strategy. I really blew the Battle of Midway as the Americans, though.

So, let’s talk about a way in which I hope to improve on the old classic: movement. Carriers at War plays out on a 20-mile hex grid; Random Carrier Battles currently tracks positions down to 10 meters; rather than a five-minute time step, I use a six-second timestep (organized into ten steps per one-minute turn) for movement and combat. This lets me do all sorts of fun things which 1992’s processing power did not allow, which I’ll get to shortly. It also causes me a great deal of trouble, which I’ll gripe about first.

The short version is, the kinematics are hard.

The slightly longer version is, there’s a lot of math involved in working out just how game entities ought to move. Warships aren’t much of a problem, because it turns out that warship maneuvering is pretty straightforward1. Aircraft, however, get a little tough. Not only do I have to consider everything I do with warships, I have to account for performance differences at altitude, as well as rates of climb and descent beyond which aircraft must either decelerate or accelerate. I don’t have the design fully worked out for that yet, I’m afraid, so I can’t say much more yet. Rest assured it’s complicated.

So, what does that enhanced positional and temporal resolution buy me above Carriers at War?

Better simulation of strike range
This is the biggest win, in my opinion. With such a high temporal and positional resolution, I can simulate fuel consumption to a much greater level of accuracy. As such, I don’t need to limit myself to Carriers at War’s fixed strike ranges2. The TBD, for instance, gets a with-torpedo range of 90 miles. I’ve seen other figures give a combat radius of 150 miles, and still others give a range (not radius) of 435 miles with a torpedo. By tracking fuel, I can, to some degree, ignore the trickier combat radius figures2, and simply grab a plausible cruise range figure. If I mix in some reasonable modifiers for speed, altitude, weight, climbing and descending, and maneuvering, suddenly I have a system which doesn’t need to work with combat radius at all. Players can launch strikes well beyond range if they want to; they just need to know that they’ll have to either deal with losing planes to fuel exhaustion, or follow the strike with their carriers.

Realistic combat behavior
The level of detail in kinematics, and the short time step, lets me make emergent some behaviors which might otherwise be the result of dice rolls. For instance, are Devastators running in on your carriers? Turn away from them, and the slothful American torpedo bombers will have to chase you, running their fuel down and exposing them to the depredations of your CAP and your escorts’ AA. Dive bombers rolling in on you? Throw the helm hard over to throw off their aim.

Many of these behaviors can be made to happen automatically: ships under dive bomb attack will make evasive turns on their own, for one. I haven’t yet decided which behaviors will end up being automatic, and which will be tactics set up by the player, but my aim is to do the low-hanging fruit for the player.

A notable exception to the above model is air combat: my current expectation is that the six-second combat step will prove too large for air combat (and relatedly, that emergent air combat behaviors will prove very complicated to code), and that the best way to handle it will be to put planes into a furball object inside which combat is handled in an abstract manner.

Exploration of unexplored formation options
Allowing the player relatively detailed control over formations, and keeping track of positions in similar detail, allows players to try some unusual tactical ideas. For example, the Japanese were not in possession of shipboard radars until fairly late in the game. What if, in some hypothetical battle, they detached some escorts from the main task force to make a search line a few miles toward the threat? Perhaps they could better direct their CAP to meet incoming threats.

That’s only one example. Undoubtedly there are others which haven’t occurred to me yet.

Those are at least a selection of the benefits of an approach with a greater focus on direct simulation, as opposed to a more traditional hex and counter approach. We’ll see how they turn out.

  1. At least to the fidelity I plan to simulate. There are lots of fascinating behaviors when you introduce multiple screws into the mix, but given that Random Carrier Battles is still, at its essence, a game of task forces, I don’t intend to allow players to give orders that detailed.
  2. The reason they’re so fiddly is that nobody ever talks about their assumptions: what load, exactly, constitutes a combat load? Is range deducted for reserve fuel and the time spent forming up? Are allowances made for maneuvering over the target? These are three of many questions left unacknowledged by most authors of military references.

Announcing Random Carrier Battles

Coming soon, or at least at some point down the line, from the Softworks division of Many Words Press, Random Carrier Battles:

random carrier battles main menu

Random Carrier Battles is a computer wargame simulating aircraft carrier warfare at the operational level between the mid-1930s and the end of the Second World War. It features a user-friendly design system for carriers, escorts, and aircraft, along with a large library of predefined types for your convenience. Planned features include a scenario editor and a random scenario generator, along with some premade scenarios covering major battles in the Second World War.

If you listened to Episode 12 of The Crossbox Podcast, you’ll remember my goal for the design system: create something just complex enough to adequately capture the different schools of carrier design in the era in question.

random carrier battles design

In scenarios, the player fills the role of the admiral in command, controlling the composition and disposition of the task force or task forces under his control, as well as the tempo and target of air operations. Hands-on admirals will be able to control aircraft handling down to the individual plane aboard their carriers; big-picture admirals will be able to delegate those to the computer.

Both kinds of admiral will have plenty to sink their teeth into strategically: Random Carrier Battles will accurately model the uncertainties inherent in carrier warfare, including incorrect spotting reports and communications failures, incomplete information about enemies, and lack of direct control over aircraft.

rcb-scenario

Obviously, this project is still in its infancy. I’ll be blogging about the development process here (at least until it’s far enough along for its own website), and sharing more screenshots and videos as things progress. Stay tuned for more information in the months to come!

The 2016 OpenTafl Computer Tafl Open approaches!

That’s right, ladies and gentlemen, one month until entries close. I’ve posted final deadlines and submission guidelines at the official tournament page; have a look and get ready.

During the tournament, expect coverage here, possibly to include some liveblogged or streamed games. See you in a month!

Opentaflvecken: final AI notes, plans for the future

This is the third article in a series of posts on OpenTafl. You can read the first and second parts at the preceding links.

Welcome back to the third and final entry in Opentaflvecken, a one-week period in which I provide some minor respite to poor parvusimperator. We’ve hit the major AI improvements; now it’s time to cover a grab bag of miscellaneous topics left over. Onward!

Playing out repetitions
In OpenTafl’s versions of tafl rule sets, threefold repetitions are invariably handled: by default, it yields a draw; some variants define a threefold repetition as a win for the player moving into the third repetition of a board state1. Prior to the AI improvements release, the AI simply ignored repetitions, an obvious weakness: if you found a position where you could force OpenTafl to make repeated moves to defend, you could play the forcing move over and over, and OpenTafl would obligingly find a different way to answer it until it ran out and let you win. No longer! Now, OpenTafl is smart enough to play repetitions out to the end, using them to win if possible, or forcing a draw if necessary.

It turns out, as with everything in AI, this is not as simple as it sounds. The problem is the transposition table. It has no information on how many times a position has been repeated, and repetition rules introduce path dependency: the history of a state matters in its evaluation. Fortunately, this is a very simple path dependency to solve. OpenTafl now has a smallish hash table containing Zobrist hashes and repetition counts. Whenever a position appears, either in the AI search or in the regular play of the game, the repetition count is incremented. Whenever the AI finishes searching a position, it is removed from the table. In this way, at any given state, the AI always knows how many times a position has occurred. If the position has occurred more than once in the past, the AI skips the transposition table lookup and searches the position instead. This seems like it might cause a search slowdown—repetitions can no longer be probed—but in practice, it’s turned out to have almost no effect.

Move ordering improvements
I discussed move ordering a little bit in the second article, but I want to go into a little more depth. Move ordering is the beating heart of any alpha-beta search engine. The better the move ordering, the better the pruning works; the better the pruning works, the deeper the AI can search; the deeper the AI can search, the better it plays. Early on in OpenTafl’s development, I threw together a very simple move ordering function: it searched captures first and everything else later. Later on, after the transposition table went in, I added a bit to try transposition table hits in between captures and the remaining moves. The move ordering used Java’s sort method, which, though efficient, is more ordering than is necessary.

Late in the AI improvements branch, when I added the killer move table and the history table, I decided to fix that. Move ordering now does as little work as possible: it makes one pass through the list of moves, putting them into buckets according to their move type. It sorts the transposition table hits and history table hits, then searches the killer moves, the history table hits, the top half of the transposition table hits, the captures, the bottom half of the transposition table hits, and finally, any moves which remain. Though there are two sorts here instead one, since they’re much smaller on average, they’re faster overall.

Puzzles
Okay, this one isn’t exactly an AI feature, but you’ll note that the title doesn’t limit me to AI future plans only. It also turns out that this isn’t much of a future plan. Puzzles are already done on the unstable branch, so I’ll use this section to tell you about the three kinds of puzzles.

The first is the least heavily-annotated sort, the one you might find on the hypothetical chess page of a newspaper: simply a rules string, a position string, and a description along the lines of ‘white to win in 4’. OpenTafl supports these with the new load notation feature: paste an OpenTafl rules string into a dialog box, and OpenTafl will load it. (There’s also a new in-game/in-replay command which can be used to copy the current position to the clipboard, ctrl+c and ctrl+v being nontrivial for the moment.)

The other two are closely related. They start with a standard OpenTafl replay, then use some extra tags to declare that the replay file defines a puzzle, and tell OpenTafl where in the replay file the puzzle starts. The puzzle author uses OpenTafl’s replay editing features to create variations and annotations for all of the branches of play he finds interesting, then distributes the file. When loading the file, OpenTafl hides the history until the player explores it. The two closely-related kinds I mentioned are loose puzzles and strict puzzles, the only difference being that loose puzzles allow the player to explore branches the puzzle author didn’t include, while strict puzzles do not.

OpenTafl has all the tools you need to author puzzles, although, at present, you will have to do your own position records. (Sometime down the line, I’d like to add a position editor/analysis mode, but today is not that day.) The README will have more details.

You can expect two or three puzzles to ship with the OpenTafl v0.4.4.0b release, along with all puzzle-related features.

Future evaluation function plans
I mentioned before that there are some weaknesses in the current evaluation function, and that some changes will be required. I’m becoming more convinced that this is untrue, and that what I really ought to do is an evaluation function which is easier for humans to understand. The current evaluation function just places an abstract value on positions; the one I’d like to do uses the value of a taflman as an easy currency. In doing so, I can ask myself, “Would I sacrifice a taflman to do X?” Having that as a check on my logic would be nice, and would prevent me from making dumb logic errors like the one in the current evaluation function, where the attacker pushes pieces up against the king much too eagerly.

This may also require more separation in the evaluation function between different board sizes; sacrificing a taflman in a 7×7 game is a bigger decision than sacrificing one in an 11×11 game. I may also have some changing weights between the opening and the endgame, although, as yet, I don’t have a great definition for the dividing line between opening and endgame.

Anyway, that’s all theoretical, and undoubtedly I’ll be writing about it when I get to it, as part of the v0.4.5.x series of releases. In the meantime, though, I have plenty to do to get v0.4.4.0b done. I’ll be testing this one pretty hard, since it’s going to be the next stable release, which involves a lot of hands-on work. The automated tests are great, but can’t be counted on to catch UI and UX issues.

Thanks for joining me for Opentaflvecken! Remember, the AI tournament begins in about three and a half months, so you still have plenty of time to hammer out an AI if you’d like to take part. Hit the link in the header for details.

  1. This isn’t exactly intuitive, but the person moving into a state for the third time is the person whose hand is forced. (Play it out for yourself if you don’t believe me.) Although it’s traditional to declare a threefold repetition a draw, I think it works better in tafl if the player making the forcing move is forced to make a different move or lose.