Tag Archives: coding

OpenTafl v0.3.1.0b: spectator mode

Posted by

OpenTafl hit another major development milestone over the weekend: spectator mode! I believe that makes OpenTafl the first real-time-viewable location for online tafl play in the world.

I mentioned in one of my last tafls post that OpenTafl’s architecture has made many of these features extremely easy. Before I let you go today, I wanted to bust out the old object relation chart builder thingy and talk about what I mean.

This is the rough structure of OpenTafl, as relates to the actual play of games. The Game object (along with its children, not shown here) encapsulates the rules. It has methods to play the game: you can ask the Game object who is up to move, and give it a move (in the form start space, end space) to advance the state of the game. It also handles the game clock and a few other bookkeeping tasks.

The CommandEngine object wraps the Game object, and with objects of type Player, handles all the upper-level bookkeeping: sending events to the UI, tracking which player corresponds with the physical human player, and so on. Higher-level components host a CommandEngine object, and correspond to one or more of the Player objects.

When the CommandEngine wishes to notify a higher-level component that something has happened, it uses the Player object. The higher-level components interact with the CommandEngine primarily through the Player object, sending moves and receiving their results through that interface.

Let’s look at an example: a human player, playing a network game against an AI player running on a different computer.

Start with the human player. He’s sitting at the keyboard, looking at the in-game UI. He makes a move. The GameScreen on the screen has a CommandEngine. One of the Player objects is a LocalHumanPlayer, which the GameScreen uses to deliver the human’s moves to the CommandEngine. The CommandEngine delivers the move to the Game and gets the result. The move is good! Hooray! The CommandEngine takes the result and delivers it to the other Player’s opponentMoved method.

That Player is a NetworkClientPlayer. It has a reference to the ClientServerConnection which corresponds to the server, and its opponentMoved method is wired to ClientServerConnection’s sendMove method. The move goes out into the ether.

At the server, a ServerClient receives the packet. The ServerClient has a NetworkServerPlayer as its Player.The ServerClient sees that it’s a move packet, so it parses the move and calls the NetworkServerPlayer’s onMoveDecided method, which sends the move to the CommandEngine associated with the game on the server to which the client belongs. That CommandEngine sends the move to the Game, then gets the NetworkServerPlayer belonging to the other client and calls its opponentMove method. That NetworkServerPlayer sends the move to its ServerClient, which creates a move packet and sends it.

Now, remember that this client is an AI. Does that change anything? Not really! The move packet arrives at the client’s ServerClientConnection, where it is parsed and sent to the connection’s NetworkClientPlayer’s onMoveDecided method. From there it goes into the CommandEngine. The AI plays through a LocalAiPlayer, so the move result goes from the CommandEngine through the LocalAiPlayer’s opponentMove method. Finally, the CommandEngine tells the LocalAiPlayer that it is expected to move, and the AI begins its work.

You’ve no doubt spotted how easy this makes extra functionality. The CommandEngine doesn’t care how the player ultimately makes its moves; it only cares that the player eventually responds to waitForMove by calling onMoveDecided. As such, going from simple human-on-human play all the way to networked play with spectators has required zero major architectural changes. As I said last time, robust.

You may have noticed that I wrote about AI playing over the network. This is not yet implemented, but it is the remaining headline feature for v0.3.x. I hope to build a proper, headless AI-only client, which can be started and run in the background. Ideally, it will have these features: first, it can log in and create games, with or without a password. Second, it can be passed an opponent name on the command line to join and play automatically. Third, after playing, if it created a game originally, it should leave and create a new game. Fourth, it should optionally save records of all of its games on the machine running it, so curious AI authors can investigate how it played. The above behaviors should be controlled by command line switches.

Writing it out, I don’t foresee any of those features causing too much trouble. It should be available soon, and when it is, you can expect to see a few OpenTafl AI players on the intersect server at any given time.

OpenTafl v0.3.0.0b released!

Posted by

Well, actually, it was released on Thursday, but parvusimperator needed some space filled on Saturday, so here we are.

OpenTafl v0.3.0.0b is a major milestone release, as you can tell by the version number increment. It brings support for network play and, as far as I know, is the only real-time tafl game with support for a proper game clock built-in. From now on, there will be a server running at intersect.manywords.press, which is the default setting in OpenTafl. Selection of server is user-configurable, and anyone can run a server by using the –server command line option, and optionally –threads <#> to indicate how many worker threads the server should run.

In other news, OpenTafl now lives primarily at Bitbucket: you can find the link (and the link to the updated version) on the OpenTafl website. Bitbucket has a built-in bug tracker, so if you encounter any issues, file them over there1. The source will continue to be mirrored at the old Many Words hgweb instance, but those updates will lag by a day2.

Since I have a few extra days3 to write this, I may as well go into a little more detail on OpenTafl’s server architecture, for the curious.

For maximum scalability, the OpenTafl server does as much work as possible on a set of worker threads, which pull tasks from a priority-based task queue. The task queue has three separate internal queues: a high-priority, standard-priority, and low-priority queue. Tasks are preferentially executed from higher-priority queues, interleaving low-priority queues as necessary to prevent total starvation of the lower-priority queues4. When a client connects to the server, a client thread is created. This client thread has the sole task of taking incoming data and pushing it to a handle-communication task on the standard-priority queue. The handle-communication task in turn pushes tasks to the high or low priority queues.

On the server, clients can belong to no game, belong to a game, but remain in the lobby, or belong to a game and be in the game UI. The server sends lobby updates (connected users, available games) to clients in the first two states at regular intervals. Clients in-game don’t get lobby updates, to save on bandwidth and time spent sending lobby updates.

Finally, some player information is stored on the server: currently, usernames, hashed and salted passwords, and time of last login. The mechanism by which this data is stored is transparent to OpenTafl—hidden by an interface. Right now, the ‘database’ is a pipe-separated file. In the future, if I decide to go further in on the idea of server-side recordkeeping, it’ll be a fairly simple change to kick the file-database to the curb and swap in something like Hibernate+HSQLDB.

That’s where we stand now. Obviously, it’s subject to change, but generally speaking, I’m happy with it. Keep your eyes open for spectator mode and headless AI play.

1. Over there, over there…
2. Or possibly longer, until I get the cronjob working right.
3. It’s a musical tafl post, evidently. You’d better believe that my wife and I always sing ‘Extra daaaaaay!’ whenever we have reason to say ‘extra day’ now.
4. Or so it is planned. My current implementation behaves like this under light loads, but inverts its behavior at the worst possible time: as the queues begin to get busy.

OpenTafl v0.3.x: The Networkening Begins

Posted by

The time has finally come. OpenTafl v0.3.x is officially under way. You can find the ongoing changes to the source code at the Mercurial repository. I’m going to spend this post talking a little bit about the structure and organization of the OpenTafl server.

First: I decided that a thicker server was the way to go. Peer-to-peer networking is almost always more trouble than it’s worth for things like this, and OpenTafl shouldn’t be all that resource-hungry. So, the OpenTafl server will maintain the authoritative version of each game, and the authoritative version of that game’s clock. OpenTafl uses TCP instead of UDP; OpenTafl doesn’t run a lot of network traffic or need particularly low latency, and the guarantees provided by TCP are super-handy.

Second: I wanted a server which could easily be scaled up and down. Rather than work with Java’s default threading model for networking, which uses a reader thread per client to both read and do the work, I decided to write a priority task queue. Everything the OpenTafl server does, from parsing incoming communication from clients to updating the game clocks to distributing chat messages, is encapsulated in an individual task object. The task objects are pushed to one of three queues, corresponding to high, standard, or low priority. Higher-priority tasks are executed preferentially, unless there’s a large backlog of lower-priority tasks. This lets the number of worker threads be subject to user configuration. Finally, to distribute load, the OpenTafl server spreads out repeated tasks over a number of buckets in the period of repetition: clients get an updated game list every 30 seconds, by default, but only one in thirty clients gets the game list per second.

Third: Clients are expected to do some heavy lifting. The client gets a server clock update every five seconds, and has to maintain its own clock for display purposes in between. Although the server runs the authoritative version of the game, each client also keeps a full copy of the game. This lightens the burden on the server, which does a lot, and pushes it to the clients, who don’t do much, relatively speaking.

Those are the big features. I’ve run some successful tests over the past day or two, successfully playing out games over the network. I have more features to do before I can make an initial public release, but I expect to have one for you in the next few weeks.

Oracle v. Google: Apocalyptic Subhead

Posted by

Bringing you only the finest in topical writing, it’s your Soapbox contributors.

So, Oracle v. Google. First, some backstory. In 2009, Sun Microsystems, the creator of Java, was acquired by Oracle, Inc., Larry Ellison’s database outfit. At around the same time, Android was in the middle of taking off. (The HTC Dream/T-Mobile G1 was released in October, 2008.)

Android, of course, is the most widely-used mobile operating system in the world, and something your humble author works with on a daily basis. Developed by Google, Android has two parts: a low-level operating system, powered by Linux, and a framework running on top of it, written in Java. … but not exactly. Google re-implemented some of Java’s APIs, for reasons of developer familiarity. I’ll pause for a moment here and give you some metaphors for APIs, in case you aren’t also a developer.

At its most basic, an API (which stands for application programming interface) is a list of capabilities a certain piece of code exposes to the world. First consider a racing rowboat, with a team of oarsmen and a coxswain in the back. The rowers have a simple API: there is one function (sometimes called a method or a procedure) called ‘stroke’. The coxswain doesn’t necessarily need to know how the oarsmen row, but he does need to know that, when he says ‘stroke’, the oarsmen will all row at once.

Next, consider a car. It presents a slightly more complicated API: ‘go faster’, ‘go slower’, and ‘turn’. In modern cars, the API is implemented by the gas pedal, the brake pedal, and the steering wheel. In the early days of motoring, this wasn’t necessarily so: the Model T, for instance, used a very different control scheme. The important point is that both the Model T and a Tesla Model S implement the same API, no matter how different they may be in the details.

Finally, consider a dictionary. Say you invent a language and create a dictionary for it. Your dictionary is protected by copyright, but your language is not. US copyright law says that you can copyright expression, but not information or data. Your language is information, but the definitions in your dictionary are expressive, creative content. So, although your dictionary is copyrighted, someone can come along and rewrite all your definitions. By doing so, they have created a new work, and you have zero rights to it: they’re using the freely-usable data (the words which compose your language) that you have collated, and making new content where copyright would otherwise be an issue (the definitions).

So, what does an API entry look like in Java?

public String toString()

There are three parts here. ‘Public’ means that anyone who includes this piece of code in their own piece of code can ‘see’, and therefore use, the function. ‘String’ means that the function returns a value of type String. (A String is a piece of text.) toString() is the method name. (There is a fourth part; the parentheses enclose the arguments, the information which someone who wants to call the function must send to the function. In this case, there are no arguments.)

An API is something like a mixture of all of those metaphors1. It’s a way to lay out the functionality of a piece of software, and functional works are generally not subject to copyright. On the other hand, an API is also a description of the functionality of a piece of software, and descriptions (like dictionary definitions) can be copyrighted.

That brings us back to the matter at hand, re-implementations of Java. Two other projects with that aim predated Android: GNU Classpath and Apache Harmony. You’ll note that neither calls itself Java: Oracle, by way of Sun, owns the trademark for the term ‘Java’. Now, Java’s APIs are organized in groups called packages, which have names, for instance, like java.lang (core functionality in the Java language). Crucially, Sun never thought it could copyright those names. It could copyright the implementations: for instance, there’s a method called Math.max(number, number), which returns the larger of two numbers, belonging to the java.lang package. Its full address is java.lang.Math.max. Despite the occurrence of ‘java’ in the package name, Sun never asserted ownership over the structure of the API: it was broadly accepted in the software industry that API definitions were functional, not expressive, and therefore not subject to copyright.

In 2012, though, Oracle looked at Google and thought to itself, “Hmm. I want a piece of that sweet, sweet Android pie. How can I get my hands on that?” The answer? Assert copyright over the Java API. Oracle sued Google in the US District Court for the Northern District of California. The jury ruled that there was infringement, but hung on Google’s fair use defense. Rendering the jury’s verdict moot, Judge William Alsup4 additionally ruled that APIs aren’t copyrightable at all, under a certain clause in the Copyright Act5 which states that procedures, processes, systems, and methods of operation, among other things, are not subject to copyright. Oracle appealed to the Court of Appeals for the Federal Circuit, which overturned Alsup’s ruling that APIs are not copyrightable, and remanded the case back to Alsup’s court to hear arguments over fair use, which is where we are today.

Before I go on, I want to remind readers that, from a practical standpoint, I’m on Google’s side. I don’t think that APIs ought to be copyrightable, for reasons I’ll get into later. That said, having read Judge Alsup’s decision in the original case, and the CAFC’s decision overruling that decision, I think that the CAFC probably ruled correctly, exclusively as a matter of law, in Oracle’s favor. Oracle argued—convincingly—that, although a method like toString(), the example above, may not be copyrightable in itself, the arrangement of methods into classes and those classes into packages constitutes a taxonomy, which an earlier case found to be subject to copyright. In the same way that writing, “It was the best of times, it was the worst of times,” would not infringe on Charles Dickens’ copyright, but inserting the whole text of A Tale of Two Cities into this post would, copying a single method from an API is different than copying an entire API.

Unfortunately for the world of software, Oracle’s argument—that the organization of the API is expressive, and therefore subject to copyright—seems correct to me. There are infinite ways to organize an API, and deciding on one of those is an expressive process which takes creativity. Certainly, there are well-structured APIs and poorly-structured APIs, and there are no hard and fast, mechanical rules for how to design the former as opposed to the latter. An API is not like a general-purpose English dictionary, where there is only one reasonable arrangement for the words and definitions, the alphabetic and that arrangement is therefore purely functional. It’s more like a Chinese dictionary, where there is no purely alphabetical arrangement for the words. To arrange words in a Chinese dictionary, the dictionary author has to design a taxonomy or an arrangement, and that, again, is a creative process6.

Up until now, I’ve spoken of the law as it stands. How the law stands is, in this case, different from how the law ought to be. Although the organization of an API is taxonomic, and therefore subject to copyright, APIs need a special exemption. I’ll provide a few examples of products which, under the case law established by the CAFC, would be infringing.

First, and most ironic, we have… Oracle’s flagship database product. Almost every database in wide use today uses a programming language called SQL to manage and query the database. Oracle DB is no exception. Oracle did not, however, invent SQL: that honor falls to IBM, which created the language in the early 1970s. Oracle re-implemented it, evidently without obtaining a license, in the late 1970s, and SQL was not released as an ISO standard until 1986. Since Oracle was founded, and went through its initial growth, by infringing IBM’s copyright on the SQL API, IBM has plausible grounds to literally sue Oracle out of existence7.

Second, we have Linux, as well as all the GNU utilities. In the 1980s, Unix was an AT&T product, and antitrust judgements had forced AT&T to license Unix freely. When AT&T spun off Bell Labs, those judgements no longer applied, and Bell Labs began to sell Unix as a commercial product. The GNU project, and eventually Linus Torvalds, wrote clean-room implementations of the Unix kernel, which became Linux, which now powers the larger part of the Internet. Nokia, the owner of Bell Labs, can now hold the whole Internet hostage. (Fortunately, I doubt they will. Nokia tends to be pretty chill.)

Third, and most compelling, we have literally every non-Apple computer in existence today8. In the 1980s, IBM released the IBM Personal Computer, from which we get ‘PC’. Almost immediately after that, dozens of competitors released IBM PC-Compatible computers, which re-implemented the low-level API by which programs written for the IBM PC interacted with the operating system and the computer hardware. The presence of a de-facto standard allowed competitors to enter the marketplace, and as the PC market grew, Microsoft released MS-DOS and Intel figured out its own expansion card standard. When IBM tried to go proprietary, the consumer PC market—now almost entirely independent from IBM—moved to the Windows/Intel standard that has persisted to this day. Without IBM’s initial innovation, and the freedom of other manufacturers to re-implement IBM’s standard, we wouldn’t have the vibrant personal computer market we have today.

So, the law is wrong. We can’t fix that in this case. What can we do? Google is trying to claim a fair use defense, and may yet prevail, but I don’t want to speculate on the odds. Provided that APIs are copyrightable (and, right now, as a matter of law, they are), Google’s use was probably not protected by fair use. My read of the trial suggests that, in general, Google argued well and Oracle argued poorly. With any luck, the jury will agree.

What if they don’t? The result is bad for the software industry, but not as apocalyptic as some might claim. There is no copyright concern as far as using an API goes: that isn’t the issue at hand here. The issue is reimplementation, which is a driver of innovation and market expansion. We will likely see fewer products which are designed to take the place of other products, because such projects are now risky on copyright grounds, and depend on the good will (or free licensing) of the copyright holder.

We’ll also probably see a return to ‘not invented here’ as an objection to using open products—unless they were designed from the ground up to be different from other, existing products covered by copyright, the risk, for corporate entities, is too great.

Finally, it’s also bad for Java. Closing a platform tends to kill it; see the IBM example above. Even if that doesn’t happen, Oracle’s behavior here will undoubtedly have a chilling effect. Although I just said that this suit doesn’t have a major impact on day-to-day usage of Java, what it does do is demonstrate that Oracle is willing to push the boundaries of IP law in pursuit of a quick buck. If that’s the way they want to behave, they’ll have to deal with the consequences: people are going to run away from Java.

Fortunately, Google appears to have won, according to the news today. More on what that might mean after I read enough to synthesize an opinion.

1. My wife, who holds a seminary degree, often talks about heresies2 as regard the Trinity, and how most common metaphors for the Trinity end up espousing one of those heresies. My usual response is, “Yes, but there’s no such thing as a perfect metaphor; a perfect metaphor is just the thing you’re trying to describe.”
2. In the technical sense; that is, beliefs incompatible with lower-case orthodox Christian doctrine.
3. (There is no third footnote. I forgot to update the numbering when I removed it, and can’t be bothered to change it now.)
4. His middle name is ‘Haskell’, which the programmers and computer scientists in the audience will find amusing.
5. See here for more; you’re looking at section b.
6. To my knowledge, which is very limited, because I am not a lawyer, this has never been tested in a US court, but my feeling is that the arrangement of a Chinese dictionary would also be copyrightable. See this article and point 5 in this blog post for more on Chinese dictionaries.
7. Your author would watch that case.
8. I don’t know if Apple computers count here, so I’ll leave them out.

OpenTafl v0.2.4.7b, and a finalized engine protocol

Posted by

The biggest news first: the OpenTafl Engine Protocol is officially version 1.0. Future changes to the protocol will be backward-compatible, and will contain some way of alerting OpenTafl that you support a version greater than 1.0, but that’s not in the near term. The OpenTafl Notation Spec has changed in a few minor rules-string-related areas, particularly king strength; make sure you update your engines based on that. The Notation Spec is also finalized: changes will be backward-compatible for the foreseeable future.

With engine mode all set up, I spent some time hammering out bugs in the OpenTafl AI, and its external engine client functionality. The 2.4.x series has been almost entirely bugfixes since my last tafl post, so I have very little news on the recent-developments front. As always, you can read about the little changes in the latest README file, available as part of the OpenTafl download.

As I said in the last post, I’m taking a break to work on my schedule generator for Out of the Park Baseball, which should take me a week or two of coding time; after that, I hope to get the Lanterna-based UI working in a raw terminal context, so that it doesn’t depend on a system with a GUI. (The default will probably remain Lanterna’s Swing-based terminal emulator, but having a headless version will make running the tournament easier.)

Once I’ve finished that, it’s on to networking! Though it’ll be a huge pain, I’m looking forward to wrapping up that feature.

OpenTafl v0.2.4… .2b: now with extra hotfixes

Posted by

I’ve released another new OpenTafl version, this one with two major features:

First, tablut games. Two tablut variations are included. The one listed as ‘tablut’ is standard tablut, according to the rules given at Aage Nielsen’s site: armed king, strong at the center but weak elsewhere on the board. The one listed as ‘Foteviken tablut’ is, again, from Aage Nielsen’s site, and features something altogether new for OpenTafl, a feature I had planned for but had not yet used: attacker fortresses, used here for hostile attacker camps. In this version, the attackers may move around inside their starting areas, but may not re-enter them from the outside. Defenders may not enter the attacker fortresses. Additionally, the attacker fortresses are hostile to the king. In exchange, the king is always strong. This represents an interesting middle ground between corner escape rules and edge escape rules: the king’s side must still play for the corners of the board, but needs not play for the corners specifically.

Second, the implementation of the ‘rules’ command. In a game, you can type ‘rules’, and you’ll get a dialog window showing the rules of the game you’re currently playing, or the replay you’re currently viewing. Helpful if you lose track of them, or if you want clarification on a certain point of the rules for a replay.

In other news, I’ve made some small improvements to the UI, specifically the scrolling labels used for the help and rules windows, and for the in-game status display, and have compiled two more of Tim Millar’s excellent annotated games (from the World Tafl Federation) into OpenTafl replay files.

This is likely the end for 0.2.x; I hope to do some serious testing over the next week or two, as well as finalize the engine protocol. Look for a 0.2.x final in the next few weeks.

OpenTafl v0.2.3b release, and a vision for 0.3.x

Posted by

OpenTafl v0.2.3b has been released. I won’t go into its myriad features, leaving that task to my previous post, and the README included with OpenTafl, but I do want to talk briefly about the next release, and what it’s going to bring to the table.

0.2.x has been a little less focused, with its three major features (by my count, external engine mode, AI self-play, and replays/saved games), but 0.3.x is going to be laser-focused on adding network play. This will happen in a few stages.

The architecture
I’ve made good progress on this stage already. I will add a server mode to OpenTafl, which will hold canonical representations of all games in progress, and send move updates and clock updates between clients over a TCP connection.

I chose a pure server-client model to limit NAT issues: peer-to-peer networking is super-annoying, while server-client lets clients initiate the connection and therefore know to do all their fancy address translation. I chose TCP to limit the amount of bookkeeping I’ll have to do. UDP requires acknowledgement and resending; TCP handles all of that as part of the protocol, and given that an OpenTafl server won’t send traffic to any given client at very high rates, the overhead is acceptable.

The protocol
I intend to recycle the OpenTafl Engine Protocol pretty hard: guaranteed ordering and delivery, as you get with TCP, solve a lot of its problems in unreliable environments. (It will require some enhancements to compensate for latency in clock updates.) No reason to do more work than necessary.

Unlike external engines, network clients can’t run so headlessly—at a minimum, they need to display the game for the human on their end, so I feel that clock updates ought to come a little more often than ‘on turn changes’. It’ll probably end up being on turn changes or every five or ten seconds; the client will handle intermediate counting-down, while the server will keep track of time authoritatively.

Server features
The first version of the server will be pretty bare-bones. It will likely keep a list of known usernames and passwords, but feature no recordkeeping; it may be able to save game records on the server machine for later replay by hand.

I’d like to focus on building strong, configurable internals for the server, in case anyone else plans on running one: a thread pool to help limit resource usage, to start, and we’ll see what other options turn up.

I don’t intend on doing anything for correspondence play—Aage Nielsen has that market handled.

Client features
I hope to make the client fairly full-featured: a filterable game browser, lobby and in-game chat, the ability to load saved games as the base of a network game, and game passwords.

Tournaments and AI play features
I’d also like to build in some features for tournaments (whether AI or human) and AI players (where computers running an AI can join the server, and humans can choose the AI as an opponent).

Tournaments are kind of a tricky issue; the ideal for human players (flexibility, marking yourself ‘ready’ and getting pushed into your next match) is incompatible with the ideal for AIs (order, which would plug them into games as soon as possible). There may be a viable middle ground, or a way to configure between the extremes, or, frankly, I might just skip it. If I get the networking functional in a general sense, I have a lot of time before I need to worry about

Anyway, that’s what’s coming next: exciting times ahead, in which OpenTafl will finally fulfill my original purpose for it—a better way to play realtime games with remote friends of mine. (Granted, it has rather expanded since then.)

OpenTafl progress: v0.2.3b, and 20,000 lines of code

Posted by

This is not a notification of the release of v0.2.3b: there’s quite a bit of work still to go, as far as releases go. However, since I hit the milestone in the title last night, I figured I’d offer a little preview of what I’ve been working on. (Astute readers of Many Words Main will likely remark, “Well it clearly isn’t writing!” In this, they are not correct. It’s merely the typing I’ve failed to keep up with.)

So, what’s in 0.2.3b? Quite a lot, as it turns out; I got started on a certain big feature and couldn’t help myself. We’ll get to that in a bit. Here’s a rundown of the smaller pieces:

Completed external engine support
I finally buckled down and added the last piece of external engine support: engine-raised errors. I’d previously considered a more complicated set of engine-raised errors, but it boils down to this: there are two kinds of errors an engine can encounter, recoverable and unrecoverable errors. Whenever OpenTafl receives an ‘error’ command from an external engine, it presents a dialog box with a message provided by the engine in the command. If the error is critical (determined by the error code), the game ends. If non-critical, the game continues.

A particular IntelliJ feature greatly aided me in completing this task: there’s a quick-fix item for ‘implement interface method’, which is, to say the least, extremely handy.

Some internal changes
These mostly have to do with fixing little things which could cause trouble later. One of the principles of object-oriented design is that objects should do one thing, and some behind-the-scenes functionality was creeping into UI components. I spent some time and energy on this.

Resilience and stability updates
As this series of releases deals with adding more outside inputs to OpenTafl, I spent some time making sure that failures and edge-cases are handled gracefully. For instance, 0.2.3b will properly terminate external engines when they’re no longer required, and analysis engines are handled more like regular engines for consistency. In other news, I fixed a few random crashes I came across while working on this update.

Resolve embarrassing Copenhagen rules discrepancies
It turns out I had two things wrong about Copenhagen rules: first, edge fort escapes require the edge fort to be an invincible shape, not merely an enclosing one—that is, that black cannot break the fort no matter how many unanswered moves he gets. Second, the attacking side goes first. The second one rankles a little more than the first, especially because the first one revealed an interesting heuristic for whether or not a taflman in a chain of taflmen can be captured.

It goes like this. If a taflman is part of some safe structure (that is, a structure which contains no enemy taflmen), then you can determine whether it can be captured by, in a sense, counting liberties. Get all four orthogonally-adjacent spaces, then remove any spaces which are inside the structure, and any spaces which are currently occupied by friendly pieces. If and only if you are left with three spaces can the taflman be captured. This is a nifty little way of detecting defects in chains, taflmen which are ‘sticking out’—alone on a certain rank or file. It may come in handly sometime down the line.

And now for the big feature.

Saved games and replays
Screenshot

As part of AI self-play mode, I wrote a game serializer: a way to write out game records for later viewing. Once I had done that, I was halfway to a full replay system; and once I had a full replay system, I was immediately adjacent to loading games. OpenTafl’s replay/save system has the following features:

  • Replays and saves become the same sort of object: a human-readable OpenTafl Notation game record file.
  • Replay mode can be initiated from any game record file, or from any point in a game in progress. If the other player is not also a local human, the other player can make moves while you are viewing the replay of the game in progress.
  • At any point in a replay, you can begin a new game from that position. (Note that, at this point, you can’t return to your original game except by reloading the original game. This is a limitation which will likely be around for a long time: playable variations are likely to be a huge pain.)
  • Replay mode supports annotations, and annotations following a certain format will correctly update OpenTafl’s clock display.
  • Saved games are a shortcut of sorts: they load a replay file, play it to the end, then use the ‘play-here’ function.

I have two tasks left on my plate before I’m ready to release 0.2.3b. First, I need to test the game serializer and loader against Berserk rules tafl: the potential for more than two moves per turn (in the case of berserk moves) is one I hadn’t quite considered, and need to consider. Second, I need to write help messages for all of the new functionality.

Once I’ve released 0.2.3b, it’ll be time to give the engine protocol one final once-over, and freeze it at version 1.0, where it will remain until at least this winter’s tournament. (If critical weaknesses are revealed, it’ll have to change. If no major weaknesses are revealed, it might stay at version 1.0 indefinitely.)

Finally, I want to touch on how big a milestone this is for OpenTafl, in my estimation. Before the 0.2.x series of releases, OpenTafl was essentially a toy: a novel way to play tafl games—there aren’t a lot of modern desktop clients—but little more than that. Following the completion of 0.2.x, OpenTafl will be a tool: for learning to play tafl, through the replay and annotation functions, and for studying computer tafl, through external engine mode. We’re arriving now at the purpose I had in mind for OpenTafl—to expand the base of people who are able to translate a casual interest in the game into a deep study, by building tools to make it easier to do so. Here’s hoping it works.

OpenTafl v0.2.1b released

Posted by

OpenTafl v0.2.1b has been released here. It has almost full support for OpenTafl Engine Protocol, and the protocol specification is also near-final. (I’ll be finalizing the protocol definition in a release or two.)

The other feature on the docket for 0.2.x is a local engine-vs-engine tournament mode, which I (and, for that matter, you) can use to quantify strength gains from changes you make to your AI, by playing the current version against prior versions. I’ll provide more information on this feature as I develop it.

On tafl: time use strategy

Posted by

I wrote last month on game clocks for tafl games, and settled on something like the go game clock: main time, plus replenishing overtimes. You can find my reasoning at that link, so I won’t go into it here, rather taking the opportunity to chat about how to use the time that game clock gives you.

In undertaking any previously un-undertaken task in AI development, this question usually has an instructive answer: “How does chess do it?” Unfortunately, this case is one of the ones where the answer is a little less instructive. A perfectly functional, if not altogether optimal, time usage strategy for a chess AI is to assume that, however many moves the game has taken so far, finishing it will take 20 to 40 more moves. The AI should therefore use between 1/20 and 1/40 of the time remaining. Simple, and surprisingly effective: a chess game gets less complex over time, as pieces come off of the board.

No such luck with tafl games, though. A tafl game starts at moderate complexity, then grows significantly in complexity into the middle game, before tailing off again as the action focuses on a corner and as captures are made1. So, for fixed-time games, we want to spend a moderate amount of time on the early game, the bulk of the time in the middle game, and a decreasing amount of time in the endgame, conserving it as long as possible. For fixed-time games, OpenTafl, in its current incarnation, assumes that it’ll want to make a certain number of opening game moves (3, 5, or 10, for board sizes 7, 9, and 11), a certain number of midgame moves (6, 10, or 20), and an indeterminate number of endgame moves after the midgame. It dedicates a fixed amount of time (at present, 5%, but probably likely to increase) to finish all of its opening moves, a much longer amount of time (presently 75%) to the midgame moves, and a constantly decreasing amount of time to its endgame moves, with the remaining 20%. This seems functional enough in play with me, but the numbers will obviously be tweaked once I finish automatic self-play. (A feature which will be in 0.2.x, I’m pretty sure, given how handy it is for AI developers.)

Four hundred words in, though, and I haven’t yet covered the topic I said I wanted to cover to begin with: how do we handle overtime timing? It turns out that it’s simpler than fixed time, even: take the number of midgame moves above, use the main time for them, and use overtimes for all remaining moves. This, too, may be non-ideal—I could see some benefit to using the fixed-time framework for early game and midgame, and falling back on the overtimes only for endgame moves2.

There are some extra features I hope to add at some point: a little bit of history awareness, so that, whenever OpenTafl sees a wild swing in expected value for the current state, it can dedicate extra time to a deeper search. Another useful addition would probably be some slightly more adaptive time usage generally, with the ability to understand when the game has moved from the early game to the midgame, so that it can adjust its thinking time based on the state of the board, rather than fixed numbers of moves. That said, it’s heartening to see that my system for main time plus overtime time usage is basically what AlphaGo used in its games against Lee Sedol3.

Finally, and a little tangentially, I want to talk about OpenTafl’s success against me on various time controls. Now, I am a poor to average tafl player at best, so you should not take this paragraph to mean that I think OpenTafl has much of a chance against anyone good. Keep that caveat in mind. OpenTafl generally loses to me, and loses pretty severely, on longer time controls: this is a result of its flawed evaluation function4, which, along with alpha-beta pruning, frequently gets rid of branches that are ultimately better than the one it chooses to explore most deeply. The matches are closer with blitz timing: a 60-second brandub game proved to be pretty intense, and I only won with six seconds left on the clock. The shorter time control plays to the computer’s strengths: exhaustive reading three or four plies out, and it gets much closer to me in skill (in part because I can’t read exhaustively in such a small amount of time).

Anyway. That’s your inside look at the most recent major OpenTafl feature. Stay tuned for more in the coming weeks.

1. I should note that by ‘complexity’ here I’m referring mainly to branching factor, the quantitative measure, mixed with a little bit of my sense for what proportion of moves are worth considering, a much more qualitative one, and, for that matter, a much more unreliable one.
2. Although it may strike you that 30 moves for an 11×11 game seems a bit light, consider that it’s actually 30 turns, or 60 moves total: for most 11×11 games, the game has either ended by then, or we’re well into the midgame or late game.
3. I got sleepy just thinking about being up that late. It is my sincere hope that when DeepMind announces its match against Ke Jie or whoever’s next, that they agree to play in London. Or maybe New York. Somewhere closer to Eastern Time, please.
4. A topic I intend to go into deeper detail on in a later post, when I’m working on some cleanup and improvement.