Could you explain the AI that goes behind this? The class structure and methods, really. How are you going about this?
That would be quite a long explanation… but in brief, the important classes:
- Board: maintains game state (positions of pieces) using minimal memory. Provides useful functions that make some assumptions about rules, e.g.: get all open spaces vertically and horizontally from a given piece, or from all pieces of a certain colour. Also whether the simple win conditions have been met – white in a corner or king captured.
- “Heavy” Board: a sub-class of Board that adds more information that can be inferred from the game state. E.g. counts of pieces, whether white is surrounded, which pieces are threatened (can be captured in one turn) etc. Ideally the extra information should be able to me modified incrementally when a piece is moved.
- Transition/HeavyTransition: classes that can apply moves to a Board and can undo moves.
- Evaluator: An interface that provides a function for evaluating who is winning in a given Board position. The simplest one says 0 when black has won, 1 when white has won, and 0.5 otherwise. This is where heuristics can be implemented.
-
Search: Interface that takes an initial board state, an Evaluator, a Transition factory (that produces valid transitions for a given Board), and returns the move that produces the best looking Board. I have two implementations:
[list][li]IDDFS (iterative deepening depth-first search) using min/max with alpha/beta pruning. As this is depth-first, adding and undoing moves as it goes, memory is no issue. You can leave this running for days to evaluate positions if you want so is good for testing the correctness of other search strategies. - MCTS (Monte-Carlo tree search). This can be much better than IDDFS if you can get good playouts. This requires selecting fairly reasonable moves from any board position. Without lots of examples or good knowledge of the game this is pretty hard so I decided to shelve this strategy.
[/list]
There are other bits that get added to improve things. For example, visited sets so you can reuse values when you encounter the same state multiple times. A function for classifying moves as interesting/unintersting that can be used either for MCTS playouts or for ordering the search in IDDFS. Plus plenty of heuristics that appear as concrete evaluators.
The light-weight states almost always lose out to heavy-weight states coupled with computationally expensive heuristics. Basically you should always do more work and search less. That seems to hold for Tafl, at least for me.
On my anemic PC I get 400k nodes per second searched using a vanilla board, and about 30k/second with heavy boards and heuristics. The slower search absolutely clobbers the faster one in games. It only gives up about 1 or 2 depth but has far better evaluation of position.
Great to hear, Jono! I look forward to seeing your entry play. Well done on the speed: OpenTafl’s built-in AI can be either fast or memory-efficient, but not both, and right now, it’s more on the memory-efficient side. (To a degree. It’s all fairly heavyweight, since I’m using the same code as for the engine.) I think the best I ever did was 200-300k nodes per second on fairly beefy hardware.
I’m fascinated by your results w.r.t. old-school technique against Monte Carlo. My gut suggests that MCTS will produce better results in the long run, although you’re probably right that there isn’t nearly enough expert knowledge, nor a large enough corpus of games, to make it workable. Maybe later on in the fall, I’ll ask for game records from Aage Nielsen’s website—there have been a few thousand to maybe a few tens of thousands played there. It would be a handy thing to have.
Hydroque, if you want to look at another, less well organized approach, OpenTafl’s built-in AI package is here. Start with AiWorkspace.explore.
Anyway, OpenTafl is now up to v0.3.3.2b, which is I-swear-for-real the v0.3.x stable release, barring any bugfixes required. Network play is feature-complete, including loading saved games. v0.4.x is upcoming, with two things solidly in line: variations during replays, along with support for puzzle-type saved games, and AI improvements. There are lots of heuristics known for chess programming I’d like to try to apply here.
Interesting. I read Jono’s post, and I will take a look at your link.
I have a 1200-word post on the playable variations feature coming with v0.4.x. Or, more correctly, on a single point in the implementation: building the system for addressing variations. It turns out that naming lines of play through a move tree which can be created or deleted at will is not an altogether trivial problem, but I’ve hit upon a solution I’m not too unhappy with.
It turns out that was the hard part: building the actual variation functionality into the engine, and creating some UI to go around it, was relatively easy. I’m about 90% done with what I would consider prerelease-worthy functionality, so later today, I’m going to spin a v0.3.3.3b stable to fix a bug in game loading over the network, and a v0.4.0.0pre to demo variations while I continue to work on them. Hopefully. I’m pretty wiped out from my Saturday, so I may be a bit delayed.
Edit: double release day it is! v0.4.0.0pre and v0.3.3.3b are available now.
v0.4.1.0b is now released and, as far as I know, it’s now the only tool which allows for easy authoring and watching of annotated games. The feature list includes variations, as in 0.4.0.0pre, and now has support for variations in saved games and an in-replay UI for authoring annotated replays.
Remaining on the docket before the major AI push: a few more rules variations to support custom play at PlayTaflOnline.com, a new site for head-to-head tafl play set up by an Internet acquaintance of mine, which uses OpenTafl as a bot player.
Tried to register on playtaflonline.com but not getting the registration email. Also, I would be more comfortable with google authentication…
I’ll pass that feedback along next time I see the guy there.
Busy few days: I just put out v0.4.2.0b, which adds variants with speed-limited pieces, and a new kind of king capture option.
Releases going forward will probably slow down a lot: v0.4.2.0b is basically feature-complete, and my next task is AI improvement, which will take a long time and a lot of testing to be sure that I’m actually making a positive difference.
The stable release has gone up to v0.4.2.4b, fixing some bugs I found along the way in v0.4.2.0b. The bleeding edge release is now v0.4.3.4pre, which features a massively improved AI. It’s about 50% faster (after JIT warmup) in raw speed, and makes smarter moves thanks to some improved search techniques.
OpenTafl v0.4.4.0b has been released, the first stable version with the partially-improved AI. It also features puzzle mode, and two annotated puzzles are included.
OpenTafl v0.4.4.5b is the current stable version. It features four tafl puzzles: as far as I know, the largest assemblage of tafl puzzles in the modern era. (Which is a little sad, but I’m always working on expanding the stable.)
Do we have Ard Ri yet? 
J0, yes! Support for limited-move variants arrived in v0.4.3.x, I believe.
I’m up to 0.4.4.7b, with work under way of 0.4.5.x: the latter will (hopefully) feature some improved AI play, while the former includes all the general bugfixes I’ve had reason to implement.
Early in November, after I get back from a vacation, I’m planning on spinning up some AWS services to test both the performance of the EC2 instances and the network performance we can expect for the tournament.
With one month to go before the tournament, I’ll be tabling my other game project (which will be announced soon, but since it isn’t Java, not here) to pick up OpenTafl again for a month. On my to-do list: AI evaluation improvements, which I hope to make by letting the AI search to depth 1 and seeing why it evaluates bad positions as good positions; and some logistical setup with Amazon AWS.
AI improvements are in flight: I’ve tried and undone some interesting ideas for speed reasons, and made some improvements to the evaluation function which make it easier to adjust (albeit a bit slower, since it involves a fair bit of floating-point math).
I have one final structural improvement to make: piece-square tables, a technique borrowed from chess where the evaluation function consults premade tables relating piece type to space on the board, which give a flat score for that kind of piece being on that space. This should help immensely with making the defending taflmen flow outward and the attack taflmen flow inward. It’s also relatively simple, and carries effectively no speed penalty. I hope to have that done today.
Also on my to-do list, though this is a little less likely, is tournament support for the OpenTafl server, and UI for same in the client. This is less likely to happen in time, and my expectation is that, for 2016, at least, I’ll be running the tournament by hand.
In the last month or two, I’ve released several updates. Less interesting: bugfixes and minor improvements to multiplayer UI. More interesting: a full-featured rules variant editor, and support for arrow keys and spacebar to move pieces around the board. Much more user-friendly now.
Sounds like good progress! I am working on some non-programming projects at the moment but I hope to come back to Tafl later this year.