The final * (week 10-11 status report)

Countdown? Cut? Straw? Fantasy? You fill it in.

So, it seems I missed a week. Sorry. I don't think it really makes a difference now, there's only two days left anyway. What is the state? Well, I have a working AI for the Risk ruleset. It's a bit mediocre, but it will provide some opposition. I might tweak it a bit the next few hours, but I'm mostly done with it.

Let's see what it does... It will expand into neutral territory, it will move its troops to protect the borders of the empire, reinforce where needed and it will attack without hesitation. The last one is a bit of a problem, as it doesn't really pick its target really well. I might take another look at.

I've had some problems with playtesting though. tpclient-pywx kept crashing my X server at seemingly random times. Sometimes I could play a few turns, sometimes it'd crash three times during one turn. I ran tpserver-cpp and daneel-ai in a detached screen session and reconnected each time, but I assure you it's not really pleasant. I'm not sure what the bug is, it's probably something in X.org or it might be in kwin 4.1 or who knows where. I don't have time to figure it out now. Also, this only seems to happen with Risk. I blame wormholes bending my computer's space-time-continuum or something.

What else... I should probably take a look at Colonization orders now that they should work again, and I could help out the other students. A battle against vi1985's AI or helping ezod with his singleplayer wizard looks good to me. I suppose I should also make another human player play against my bot to see what they think. And I have to write a load of docs.

I'd also like to make a video to show off daneel-ai, and to better analyze what it is doing - reading through megabytes of log files isn't the fun way to do that. However, Starmapper seems not to cooperate with Risk (or the other way around), so that'll have to wait for a while.

So, time to finish the last small things, and that concludes GSoC 2008. *epic music*

Slippery slight slowdown (week 9 status report)

I didn't do a whole lot this week. I'm not sure why or how. Lots of other stuff to do, mostly. As an example, I completely forgot to participate in round 2 of Summer of Code, and looking back to it, it seemed like it had fun problems. :( Oh well.

I started the week by investigating the new rulesets a bit.
I started by reading Tigris & Euphrates, but I gave up after a while. Usually, I enjoy a good boardgame, but I never played this one before and I didn't really feel like reading through the rules. I should really have another try at it because nuleren has done a lot of work on it and it's probably a lot of fun, but it's a bit too much effort for me at the moment I think, I can still focus on other things. Sorry nuleren!
After that, I tried Dronesec. I miserably failed at getting it to run. Perhaps I'm just spoiled by the easiness of tpserver-cpp, but tpserver-py and the whole structure of setting up Dronesec was a bit annoying. Can't blame anyone for that, of course. On his blog, JLafont said he was going to make the whole thing a bit more usable, so I'll try again in a short while. It might be that the error I got was something different though, I should see about that.
So I mostly focused on Risk. First thing was to figure out how those wormholes work, and I talked a bit with vi1985 and jphr about it and we have it figured out now. I didn't really use them though, because I already had a system with probe orders set up and I want to keep at least one example of probe orders in my system for those wanting to learn the technique.
I also created a few more constraints to use in Risk, one to represent the armies on a planet and one for the amount of recruitable armies.

Now all that remains is to actually create a Risk AI. It's really strange how my inspiration runs dry on that task. It's probably because I don't have enough experience with the game itself though, and playing a match against oneself quickly becomes boring and tedious in switching the interfaces. Chicken and egg, much? Well, small steps I suppose, and make it incrementally better.

Modularity (week 8 status report)

My goal for this week was to split out the RFTS-specific code into modules in a reusable way. I think I managed to do this in a fairly nice way. A rule file can now specify a list of mods to be loaded. These mods contain code that moves the data from the cache into the constraint store and the processed data back to the cache. The mods can also specify additional rules, constraints and functions.

After a while of moving functionality around with this system, it seems very flexible to me. I currently have a "basic" mod that will copy all the object data from the cache to the constraint store. It would however be possible to write a "light" mod that only copies some data to the store each turn, but also initializes the store with long-term constraints for the static data, like star system locations in RFTS. It might be possible to save some time on rule matching that way. One could also write a "messages" mod that adds the message board data to the constraint store and allows one to post messages, and the same for a "designs" mod. I've also added some mods for specific rulesets. This allows, for example, to add a constraint about the turn type (in the 3 turn cycle) in a RFTS game.

I started researching the Risk ruleset being created by jphr for SoC in order to test how usable this modularization really is, and I immediately bumped into a big problem. Up until now, I didn't support any client/server communication in the rule evaluation. However, Risk seems to require probe orders to give information to the client about what planets are adjacent, so I had to take a look about implementing those (note: the new wormhole patch might have lifted this requirement, I should investigate). The final result is that I allowed the Python code that can appear inside rule files to use the cache, rulesystem and connection directly so that it is possible to place probe orders. It's a bit ugly, but it works. I assume mod and rule file writers will use these variables sensibly, as abusing them can confuse the bot pretty hard.

Today, I extended the documentation at the wiki a bit. It still needs work but I think that it might be possible for those longing for adventure to write their own AIs with the current codebase. Remarks on the documentation (or anything else, of course) are always welcome.

Oh, and Sunday I qualified for the second online round of Google Code Jam. I doubt I'll make the next round though unless I have a very lucky insight in one of the hard problems. Still, it's fun to be among the top 2500-or-so.

I'm a bit at loss on what to do next. Since RFTS has a nasty bug that seems to prevent colonization (reminder to self: I really need to file those bugs in the tracker) and xdotx doesn't seem to be around, I don't feel a lot for working on that ruleset. So I think I'll take a look at the SoC rulesets (Risk, T&E and DroneSec) to get a (basic) mod for each of them. Then I'll focus on one of them to create a decent bot. It'll probably be Risk since vi1985 is doing that too, T&E is too complex for my small brain and I don't know too much about DroneSec yet (apart from that it looks fun). I hope this will help the others a bit with their rulesets.

(week 7 status report)

I've lost track of the days. I heard it was Friday yesterday, so time for another report...

So, as said last week, I wanted to do longterm storage and perhaps some parsing this week. I finished longterm storage and updated the rfts-rules ruleset to remember the list of unvisited stars between turns. I also did the parsing and updated the rules to use a CHR-like syntax. A lot more readable and easy to write! And I made some small improvements to the framework.

Next week I'll try to separate the RFTS-specifics from the framework. I'm not entirely sure yet how the end-user interface will look like, so I'll have to think a bit about that first. But when that is done, the framework is essentially done. I can then start giving some more interesting behavior to the bot and let a couple of them fight against each other.

Which reminds me. I've made a small video (using Starmapper - fun thing btw) of daneel-ai colonizing an undefended universe. Going on a bit about starmapper: the main problem here is it can only download information from one player and thus needs a guest account with full visibility to be able to view and map everything in a multiplayer game. A nice project would be to add some sort of report dump to the server, which can then be used by Starmapper to generate the pictures. The reports/pictures would be disabled (or inaccessible until the game has finished) for public servers. Another option would be to allow Starmapper to log in with different accounts and download and merge the information, but that doesn't sound as elegant. Something to think about, perhaps.

Tension rises (week 6 status report)

It's a bit overdue, yeah, but let's see anyway...

So, from last week's status report, the plan was to externalize the rules to show it really is a framework. Well, I did that. And I then noticed my bot was slow, so I worked a bit on that, mainly because testing was not fun. But it still was not good enough. I then rewrote part of the bot to use an external constraint processing system. It's still slow for some forms of rules (not entirely sure why), but until now I managed to evade those.

I then added types to constraints. This allowed me to parse arguments of rules into Python types so I can use ints and tuples as they are meant to be used in the guards and bodies of rules.

On advice (or should I say "slight pressure") of Mithro, I then set out to create a bot that interacts a bit meaningful with the universe. It now manages to build fleets and colonizes planets. It's still not smart and mostly relies on flooding the universe, but that's a matter of writing good rules now, which goes rather fast.

I said slight pressure, because Mithro told me he didn't really like the way my project was going. He's right, of course. I didn't really focus on a deliverable AI because somewhere along the way, the focus had shifted to a framework in my mind. I suppose I failed to discuss that properly. Anyway, I tried hard to show my bot does work, so I hope mithro and nash will give me their confidence for the next half of Summer of Code.

Anyway, next week I'll implement long-term storage and rework the rules a bit to take advantage from it. I'll then finalize the parsing so it's possible to write human-readable rules and I'll then focus on writing a bot that can set up a fight.

I've also discovered a few bugs in various parts of Thousand Parsec, among which a few ones in RFTS. That was part of the goal of the project (to make RFTS more stable), but it's annoying nonetheless.

A crawling program

My bot is slow. Too slow. It takes up to 10s to apply 3 rules on a modestly sized fact database. And any bot that wants to have some good strategy needs at least a few hundred rules. And yep, time needed is roughly linear in the amount of rules, so that would take too long.

However, a bit of thinking shows why this is so slow. I can't believe I didn't notice it earlier, but it's very apparent. I'm using a very slow generate-and-test algorithm to find matching facts to my rules. Stupid, stupid: I've had classes every year where constraint propagation, backmarking, backjumping and other speedup techniques are explained and when I need those techniques, I forget all about them.

So, onwards to rethinking the fact matching. I just didn't think of it as a constraint satisfaction problem, but that is indeed what it is, and that is how it should be solved.

I think I should also revisit my database course, as things like join and selection ordering could be important here. Perhaps I could even make the whole constraint store use a (simple) RDMS instead of my own solution. It sounds like overkill (and it probably is), but might be something to keep in mind...

Back to action (week 5-ish status report)

Last week, I didn't manage to do a lot, again. I had a weekend away with a couple of friends, and then a small week off to prepare next year of student's organization. I managed to put in a few hours of work but I was so tired I didn't get a lot farther. Yesterday, I got back on track. I made my tests run, which is an impressive step forwards, and today I started on a basic parser. The parser can currently handle rules in "head normal form". The step to readable rules theoretically only exists of simple rewriting: from

ship(1) \ moving(10) <=> attacking(10)

to

ship/1 \ moving/1 <=> _var_0_0 == '1' and _var_1_0 == '10' | attacking(10)

with the latter being the head normal form (the form you have to write rules in right now). I'm not going to bother with that right now though, it's non-critical and low risk.

For the remaining of next week, I'll try to externalize the rules and functions to separate the bot framework and its logic. This will allow multiple instances of the bot to run with different "personalities". Keeping midterm evaluation in mind, this seems like an excellent goal as it basically finishes the rough framework and splits the task in 2 subtasks. I also need to search for a few hours to find a picture of myself that the internet can see. Horrible task.

Also worth mentioning is that I'm done with taking loads of time off the project. For now, I'll be able to work 10 or so hours a day. That's about what I did in a whole week the last few weeks. So productivity should lie a bit higher from now on. Hooray!

A new hope (week 4 status report)

This week saw a rewrite of the whole rule system. Based on my reflections of last time, I mostly worked it out on paper first. Yesterday and today I coded it together, and lo and behold, it worked. Few small changes from what I had on paper of course, but the main idea seems right. The commit can be found on gitweb.

So, what is left? First of all, I'll do some parsing. The rules and constraints are currently rather verbose to create. It should be possible to ease that a bit to allow easy creation of rules - that is the entire point of the project after all :). I tried my hand at it earlier but I couldn't really come up with something elegant. Anyway, I'll just code up something that does the job (= regular expressions) and if it turns out to give problems later on, I can always change it to something more powerful. Context free grammars or something, I don't have much experience with parse tree generation.

There's also a few more bugs to clear and some tests to run. Performance tests might also be useful, as I doubt the current system will be able to handle complex rules in big universes. Then again, there might be a load of speedups possible. Stress tests and profiling should help out if the need arises.

Goals for next week are: 1) getting a few more important cases to run, mostly make rules not fire infinitely and allow a constraint to be multiple times in the head. And 2) get the parsing to work. The parsing should be fairly straightforward, but part 1 might be a bit more troublesome. And I'm not entirely sure I'll be able to make it, as I'll be away most of the week to prepare the next year of our student organization. I'm not sure how much free time we'll get, neither how much of it I'll be sober enough to code. ;)

Trouble along the way (week 4 status report)

It's been such a long time... Let's see. Plans for this week were getting back on track and start with the rule representation. It worked out a bit differently though.

As noted earlier, the weekend was "lost" to studying, with an exam on Monday. That leaves just one exam left, next Monday. Data Mining this time around. Not too much work, still I'll be glad when it is over.

Then, Tuesday I managed to get some work done. I added the constraint store which seems to be in working order, and I made the bot send out a few random order to prove the whole structure can actually behave like a bot.

Wednesday, I sadly had to go to a funeral of a colleague student. Someone who is three years younger than me, in perfect health, just bam, the end. Heart attack. A professor nailed it perfectly in his speech: "this is a contradiction". Makes you think for a while...

And while I think (and hope) it's a coincidence, I've had loads of trouble with my SoC from Wednesday onwards. I've started on the rule representation, and it just doesn't seem to work out. It seems as if my class structure is wrong, I need references to all sorts of objects at the most illogical places, I have tons of code I don't seem to need, etc. Really bad signs. For example, I have pretty much no idea how my logical variables are holding up. They have a dependency with Context which seemed like a good idea at the time, but it currently means I have to create Contexts every time I want to create a unique variable, and that might spell trouble when two variables actually should be unified. Two unified variables in different contexts, only trouble can follow. There's a whole load of other small things in the current state of the code that confuse me.

Today I've been mostly thinking about that mess and especially how I got into it. It seems I got the focus on the wrong things. I thought the unification and constraint representation would be the central area with the most risk, so I started there. It now turns out I can't really use it the way it's been written. It made me think about my design process. I usually code "bottom up", in the way that I start with the small objects or the high risk parts, test them extensively, and once I know they work I'll link them together to create the bigger structure. This has always worked for me. However, not now. Now, I have interface gaps and strange dependencies. And that in <400 lines of code. I still can't grasp it.

So, back to the drawing board it was, "top down" now. I identified the external interface I need from my rule system. However, I'm not much further than that at the moment. There's a few things interacting in ways that make me twitchy. I think I'm trying to cling too much to my old code and carry those mismatched concepts into the new design, which therefor keeps failing. Or something. I'll just try to take a look at it tomorrow with a fresh head.

So this weekend, I'm going to crack down on that design. By next week, I want to have it coded and done with. Really, if that works, it's the central framework done and I can begin filling in the pieces as required.

Oh well, it's all part of the design process. At least I'm starting to know the domain pretty well by now.

Nothing to see here, move along (week 3 status report)

Exams, not much done. If you want information about routing protocols on the internet (from VLAN over link state to BGP), DNS spoofing, block designs, Polya theory or deadlock prevention I'm all here though.

Although, Wednesday, I did take a look at trying to get the constraint store working. Thinking my design wasn't really going to cut it, I started to read some papers about other CHR implementations, realizing that I'm actually getting far away from pure CHR. Well, doesn't matter. It'll be a system inspired by CHR and other expert rule systems then. I also realized there might be a bit more work to it than I thought. Oh well, I love a challenge.

So, next weekend will still be spent studying. Exam Monday, after that a bit more work on a paper that has to be handed in Tuesday. From Tuesday on I should finally be able to work on SoC again.

Also something to keep in mind: next time I'll write a 3D client. I mean, seriously, look at this beauty. All I might have to show off eventually is a bunch of spreadsheet graphs.