User:Iwanowitch/RFTS AI proposal
From Thousand Parsec Wiki
Contents |
Proposed project
The aim of the project is to create an AI client that plays a game of RFTS and manages to provide a challenge for players. There are some points in this proposal that need motivation.
First, why focus only on one ruleset? While it would be an interesting experiment to create a client that can play any ruleset in a competitive way, such a client would probably need to use learning algorithms to adapt to the particular game it is playing. Personally, having some (classroom) experience with probabilistic learning, genetic algorithms and data mining techniques, I believe it would be very hard to create a rule-agnostic AI that can play a reasonable game, even after a reasonable amount of training. Therefore, I'll only aim at one specific ruleset.
Why Reach For The Stars? It is an interesting ruleset gameplay-wise, and I believe it deserves to be one of the showcases of the TP project. As my limited experiments have quickly pointed out to me, though, this ruleset is not 100% complete and bug free. While this might slow down the creation of an AI for the game, there is also another way to look at it: the process of creating an AI will probably expose many bugs and possibly even balancing issues or inconsistencies in the ruleset. Tyler Shaub (xdotx), the creator of RFTS, already mentioned he would be working closely together with whoever else does something with his ruleset - I would definitely keep him to this promise if I'm developing the AI. Thus, this project would almost certainly have a beneficial effect on the stability and polish of RFTS.
Onwards to more technical details. I would code the bot in Python. First, because there is quite some existing and well-tested Python code in the project and I don't think it would add a lot to recreate all that stuff in yet another language. This project would either base the bot off libtpclient-py or the existing AI code in tpsai-py if it can be reused. Secondly, Python is a pretty high-level language - I feel more for Python than for C++, personally. Thirdly, I have to admit I don't know that much Python myself, but I've been thinking about learning it. This project would force me to do so, which I'd see as a tremendous personal gain: I'd finally be able to make up my mind on the Perl vs Python debate (don't mention Ruby). :)
I think game AI is of highest quality when the high-level algorithms are simple and deterministic. I don't know whether to blame difficult debugging, inappropriate techniques or just not enough experimentation of game developers, but I never witnessed a good "messy" game AI. I think there is a reason why most commercial games still have rule-based or finite-state AIs: they are of a much higher quality. As such, I would like to keep to the "KISS" paradigm. The basic AI will consist of a set of weighted and parametrized rules that will aid the bot in deciding what to do next. Rules are to be things like "When under attack, build more ships" or "If you have X resource points left and these conditions are fulfilled, start developing the next technology level". These rules will be hand-crafted after careful research of the rules and some playing practice. It should, however, be easy to add new rules.
Furthermore, these rules will be parametrized (spend X% on industry) and weighted (90% chance to attack, 10% to flee when under attack). These values will be external to the rules to allow easy tweaking of them. It would be possible to easily create a defensive or a technocratic AI using these numbers.
All this isn't too hard, so if time permits it, I would like to play around a bit with these parameters. Basically, my idea was to use a genetic algorithm to refine the parameters. The ruleset provides a natural fitness function in terms of victory points, evaluation would be to let each AI play some games of RTFS against other AIs. The aim of this approach would not be to find the best possible AI (which I don't believe to exist), but instead to quickly explore the space of possible behaviours of the class of AIs proposed here, and to select some local optima, hopefully coinciding with interesting and differing behavior between AIs. If I can work out a good representation of the rules (unfortunately, I don't have my textbook with me right now - I'm sure I could find some inspiration in it), it might even be possible to add them to the genetic algorithm, too, resulting in an even bigger class of AIs.
Where possible, the design of the AI will be generalized to a framework to ease further development for AIs for other rulesets. However, I'd rather have a working semi-reusable AI than thinking 2 months about a program structure that doesn't work out. Now, don't fear that I'll deliver a heap of spaghetti, I do know my way in good program design. To name a few, Liskov, GRASP and unit tests are part of my mindset when programming.
A thing about blog/website. Last year, I didn't keep a blog or website. While I can see the value of having your experiences recorded, I personally don't much like having a blog, for the simple reason that I would spend too much time on it for too little value. I'm usually not such a rational/economical thinker, but in this case, it's extreme. When I write texts to be published (including this one), I'm a perfectionist. I try to make a sentence not sound awkward, I try to find the correct word, I re-read my final text at least three times with a day inbetween, etc. Basically, I find that way too much time creeps into it, which makes me want to postpone writing another blog post, which reinforces the idea that blogs are just time wasters, ... I'd rather not keep a blog, it'd only stress me out. And yeah, I do have experience with it.
However, I see another possibility. I'm thinking of writing an article at the end of the SoC (when I have time) with my most important experiences and advise for future generations. While it might not convey the exact same message that a blog does, I think it makes more sense in the long run, and I would personally like it more.
Schedule
I'll try to make a conservative schedule here. When I did SoC last year, it turned out I worked way faster than my schedule. However there were also more periods of down-time than I planned so it worked out pretty well in the end. :)
Before SoC I'll probably be working on a KDE project I want in for KDE 4.1. Don't fear, it shouldn't take much time away from this project. In fact, while I'm busy coding, I'll probably be on IRC so that counts for "community bonding" :). I'll also get my Python skills on a working level, and as a test for this I'll look at the existing Python code in TP until it feels natural to me.
First month of SoC might see not too much work, sorry. I've got some big school project deadlines, a friend to visit abroad, exams during June, and a week off with student's organization (so-called "predisium") to discuss things for next year. However, experience learns that exams often are an excellent time to work on all things non-school related (I'll leave the why to psychologists) - things like SoC. Since my exams shouldn't be too hard in June, that'll be okay. I would like to have at least an AI that has knowledge of the game world (which should be easy seeing the code that already exists), and a solid idea of how my rule engine is going to look in Python by the end of June. It might be possible I don't have much to show off by then - if so, I trust my mentor to evaluate my progress by the amount of sense I make when discussing my ideas with him. During this period, I think I'll work about 15-20 hours per week on average.
A week into July or something, I should have loads and loads of time to work on the project. Including a few weeks for debugging and testing, I would like to have the AI basically working at the end of July. This period will probably see me working 40h/week on average. I'm pretty sure I did more last summer, with weeks of 70+ hours, basically, doing nothing else than Summer of Code. I'm a burst-type person - you can see it as having passion for the job :)
August primarily serves as buffer period when things are spinning horribly out of control. If it all goes good, I will use the extra time to tweak the parameters using genetic algorithms, as discussed above. If I *still* have time left, I will try to refactor the design of the AI to extract a framework for possible future AIs for other rulesets. I think it'll be 40h/week for that period.
Milestones
The last date of each section is an important milestone and should be a final date. The other dates are mostly indicative for the amount of time I think I'll spend on it.
Pre-SoC study
2008-04-28 - 2008-05-12: Python study. 2 weeks of reading tutorials and writing various small scripts should be enough to grasp the important points.
2008-05-12 - 2008-05-26: Study of the TP existing Python code, to get up to par with existing code, to further expand my Python study, and to learn the coding style and habits of TP.
2008-05-26: SoC starts, by now I have got a firm grasp on the existing Python libraries and will decide which one to base the client on.
Rule engine design
2008-05-26 - 2008-05-30: Gone. Ideas might form, but I don't plan anything. I'll probably have sporadic internet access, but I can't promise I'll be able to hold extensive discussions.
2008-05-31 - 2008-06-08: Finalize the design of the rule engine, hopefully with mentor. Should provide for enough flexibility to express all wanted rules.
2008-06-08 - 2008-06-09: Set up a testing environment and a few testing goals, based on the design.
2008-06-10 - 2008-06-22: Coding, testing, debugging (it's all one process for me).
2008-06-22 - 2008-06-26: Buffer period. If it all goes to plan, start with the next part.
2008-06-26: Basic rule engine in place.
Rule design
2008-06-26 - 2008-07-06: Gone. Probably won't have any time for SoC.
2008-07-07 - 2008-07-14: Coding, testing, ... Final decision on what rules to include is made.
2008-07-14 - 2008-07-20: Further coding.
2008-07-20: Rules written, tested, working.
Extra period
2008-07-20 - 2008-07-24: Toy around with the rule engine, trying to create a some interesting behavior by hand.
The following only applies if the schedule works out and there are no huge setbacks.
2008-07-25 - 2008-07-31: Design of the genetic algorithm (textbook stuff), setup of testing environment (server configuration, being able to get stats from it, etc).
2008-08-01 - 2008-08-09: Genetic algorithm running, hopefully yielding even more good and interesting behavior.
2008-08-10 - 2008-08-16: Akademy, in my country, so I'll probably be there.
2008-08-11: Pencils down date, genetic algorithm around AI working and yielding some good results.
Bio
I'm a 21 year old Belgian student at the K.U. Leuven. I have finished my bachelor's degree in mathematics and am currently studying for a master's degree in informatics with specialization in AI. This means I have broad understanding of many things maths- and computer-related, from Galois fields and error correcting codes to the Mahalanobis distance and data mining. I also have plenty of practical programming experience, working on school projects with 50 pages of design docs, hobby programming like IRC bots and small games (none really enjoyable :), and perhaps most relevant, Summer of Code 2007 where I successfully completed a Kross/Java binding for KDE under the mentorship of Sebastian Sauer.
Discussion
You should put milestones in schedule and each of them should have dates (YYYY-MM-DD) associated with them.
State how many hours per day/week will you work on the project
Also include the information if you will write about your progress in a blog or on some webpage. --JLP 02:29, 29 March 2008 (EDT)
- Done. I put the milestones below the schedule, the working times in the schedule (it changes a bit between periods) and the blog thing at the end of the first section. Iwanowitch 16:35, 29 March 2008 (EDT)
