Tag Archives: tafl

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.

OpenTafl v0.2.0: Engine support arrives

Posted by

In experimental, incomplete fashion, but it’s sufficient for you, as a developer, to start working with OpenTafl in engine mode. You can find the new version at the OpenTafl site. The engine protocol document has been updated with the latest developments. Although I won’t be able to say for sure until I’ve finished the implementation, this version of the protocol is nearly feature-complete, and likely won’t change very much going forward.

Expect a post in the not-too-distant future on OpenTafl’s time usage planning and time-filling activities, both of which are topics of some interest.

OpenTafl v0.1.9b: the end of the line for 0.1.x

Posted by

OpenTafl v0.1.9b has been released! This release adds support for a game clock. The AI is able to plan its time usage in accordance with the amount of time it has left. Additionally, settings are now saved from run to run.

This marks the last major release in the OpenTafl v0.1 series. The next major release will be 0.2.0b, including engine mode and related features, work on which will start at the end of March or the beginning of April. Looking ahead to the tournament, I may switch around the tasks in v0.3 and v0.4 from the roadmap I put up a few posts ago—network play lets me set up each AI in its own Amazon EC2 instance and have them play that way, which simplifies the rules by letting AIs think on their opponent’s turn, and removes the need for me to figure out how to limit an arbitrary process’s resource use (although it does add some complexity in building a tournament framework).

Now that it’s feature-complete, v0.1.9b will remain the stable version until v0.2.x is ready to go. What this means for repository structure is that I’ll create a new v0.2.x branch, and that’ll be the head of the tree for dev purposes. Any bugs discovered in v0.1.9b will get patched on master and pushed into 0.2.x, if it makes sense to do so. When 0.2.x is done, it’ll get merged into master, and I’ll start a new 0.3.x branch, and so on until perhaps, someday, a 1.0.

On tafl: timing

Posted by

In a previous tafl post, I remarked on the lack of pre-defined notations and mathematical resources for tafl games. In this one, I will remark on a more fundamental deficit: namely, this is the first article I can find on the Internet which will attempt to define a standard for timed tafl games.

Surprising? Well, yes and no. Competitive tafl games are rarely played in person. The only live tournament (in the modern era, anyway) put on to date was run by the Fetlar Hnefatafl Panel, and as tournaments go, it was a fairly casual affair—the games were untimed, with a gentleman’s agreement not to take an undue amount of time per move. The other major tafl tournaments are run at Aage Nielsen’s site, and are correspondence play: timed, but not in the sense we’re looking for here.

The Fetlar panel suggests using a regular chess clock, but that seems unappealing to me. Broadly speaking, tafl games are defined by two stages: an opening, where the two sides jockey for position and control in the corners, and an endgame, where the king has left his throne and is pushing to one corner. The length of the opening doesn’t vary much for a particular board size, and generally speaking, features thoughtful, cautious play. Once the king leaves the throne to start the endgame, the flavor of play changes dramatically. The king’s side must make bold, sweeping moves, and the besieging side must split its attention between putting out fires and shoring up its leaky positions. What was a game of edging around the opponent and building one’s own structure becomes a head-on conflict.

The similarity to battle is striking, and suggests a method of timing that mirrors the structure of the game. Go players among the readership will be familiar with the concept of byo-yomi, a kind of overtime comprising a number of periods of a given length. If you don’t use all of one of your byo-yomi periods, you get it back in full. If you do use it, you move onto your next one. I suggest a tafl timing scheme using a small amount of main time, and a relatively generous overtime allocation. My thinking is this: the main time ought to be used for the opening, and once the endgame begins, the players should be nearly out and into overtime. I don’t have good information on how tafl games play out yet, but as a rough starting point, I would suggest a main time of about ten minutes, and three to five overtime periods of one minute each. More generally, I propose this mutation from a single main-time chess clock: for a given chess clock length in minutes (say, 60), divide by six to get the tafl main time (10, in this case). Divide that by ten to get the length of the overtime periods. Depending on the desired difficulty and clock sensitivity, set the number of overtimes to somewhere between two and six.

Not only does this mirror the calm-to-intense structure of tafl games, it also serves a practical purpose. Although tafl games and chess appear to have similar distributions of game lengths1, I get the feeling that the most competitive chess games are clustered around the average more than the most competitive tafl games2 are. An adaptive time control like byo-yomi frees endgames from the tyranny of the clock. Some games will end up playing out more quickly, and won’t feel clock pressure at all; I don’t feel that this is an indictment of the scheme. Some games will end up playing out at around the average length, where the clock is set perfectly: players will feel some time pressure, but have sufficient main time to lay their plans for the endgame. Some games, finally, will end up running longer. With an ordinary chess clock, a longer game would end with increasingly desperate time pressure. With byo-yomi time, the clock remains a driving force, but doesn’t get much worse with time.

Although I do propose this system for general use, I plan on different time controls for the AI-vs-AI tournament: no main time, and three ten-second overtime periods. Quick-play tournaments are known to be as effective as long-play tournaments in sorting AIs by relative skill level, and a large number of five-minute games is a much easier task for yours truly than a large number of thirty-minute games.

In final news, you can find v0.1.7.1b here, which fixes a few bugs in 0.1.7 and adds threefold repetition rules.

  1. The standard deviation for game length in number of moves for chess comes in at about 25, based on correspondence games listed here, some eyeballing of graphs, and some math based on histogram values, and 11×11 tafl games come in at 23, taken in aggregate, from Aage Nielsen’s tafl tournament history. Neither of these figures are set in stone, for reasons I’ll go into when I write up my findings.
  2. Aage Nielsen’s tournament history, above, has a large number of games between top players in the vicinity of 40 moves, and a nearly equal number at 70 to 90 moves.

OpenTafl v0.1.7b and a roadmap for the future

Posted by

This evening, I plan to release OpenTafl v0.1.7b after testing on a Windows computer. The big feature is a new UI, which should be more readable and more usable, and which opens the door to several major features: a game clock (I plan to write about timing tafl games in a later post), external AI engines and network play (thanks to a rewrite of the way commands are passed from the AI and the UI to the game engine), and, further in the future, a more easily discoverable UI, where the player can use the arrow keys to navigate the board and move pieces.

Speaking of which, here’s the roadmap. Estimated release dates after v0.2.x are not to be trusted.

v0.1.7b+ – Now to April, as I have the time
The rest 0.1.x series of releases will be concerned with wrapping up a few missing rules: the game clock and draws by threefold repetition, including (for the latter) warnings about making a move that would create threefold repetition, and status messages for both.

Once the remaining features for version 0.1.7b are released, I plan to officially announce the OpenTafl Tafl Open, and provide a space for discussion and updates among AI authors. (We already have a kinda-sorta forum, over at http://conclave.manywords.press.)

v0.2.x – By the end of April
The 0.2.x series of releases will be concerned with implementing engine support. The end-of-April deadline leaves about seven months for AI authors to build in OpenTafl engine support for the OpenTafl Tafl Open, which should be sufficient for some fairly interesting designs.

v0.3.x – Summertime sometime
The 0.3.x series of releases will be concerned with allowing more player-to-player interaction, improving the single-player experience, and implementing extra game-analysis features. Planned features for the 0.3.x series include saving and loading games by means of OpenTafl Notation game records, AI improvements, correspondence play, and a simple in-game history viewer and out-of-game replay viewer.

v0.4.x – Fall/winter
The 0.4.x series of releases will be concerned with support for real-time network play. OpenTafl will be able to run in server mode, or connect to a multiplayer server in client mode.

Other features I may try to fit in include the ability to hypothesize moves and sequences as part of the history viewer and replay viewer, although this may prove to be more difficult than I expect.

Anyway, that’s what you can expect in the next year. In the nearer future, v0.1.7b should be available no later than tomorrow morning, but most likely tonight.

OpenTafl v0.1.6.1b, and progress generally

Posted by

I’ve released a new version of OpenTafl. Among several other changes, there are two I would like to highlight.

First off, the groundwork for OpenTafl Notation-style engines is complete: there is code in OpenTafl which can produce and read in OTN rules records, code which can produce and read in OTN position records, and code which can produce OTN move records. This is a major milestone: producing and reading position and rules records is tricky, as is producing move records. (Move records should be fairly easy to read in, compared to the others; they encode a much smaller amount of critical data.) Note that the notation spec has changed somewhat, based on lessons I’ve learned over the course of my weekend of implementation. If you’ve done any work based on it yourself, you’ll want to go over the spec again. Hopefully, it won’t change much going forward, although the specification for OpenTafl-compatible engines is likely to change as I work on implementing that in the next month or two. You can see some of the work in version 0.1.6.1b: each position should provide its OTN position record, and games against the AI will report the AI’s thinking using OTN move records.

Second, OpenTafl’s memory usage has once again been dramatically reduced, to the point where it should be comfortably playable to the maximum depth at which it’s feasibly playable (currently depth 6-7 for brandub, depending on speed, and depth 4-5 for other games, depending on size and complexity) without running into memory issues, on any reasonable computer. I intend to go into a little more depth on how I accomplished this, but for the moment, you’ll just have to take my word for it.

You can find the full change logs at the OpenTafl site.