What's with the weird name ?
"Vienna", because it uses RNALib 2.1.1 from the Vienna package, "UCT" because the search algorithm is based on a Monte-Carlo technique called Upper Confidence bounds applied to Trees. A general view of upper confidence bounds is given in this lecture.
Does the bot cheat like the others ?
The other bots don't "cheat", they simply only take the secondary structure into account, disregarding other constraints. This one does fulfill all requirements (when it doesn't fail to solve), and plays like human players. The submitted solutions are not always absolutely perfect (in the EteRNA sense), because the bot uses Vienna 2.1.1 and this makes for some rare and minor differences. But the simple answer still is : this bot plays by the rules, all of them.
So, why are you writing a puzzle solving bot ?
Not sure what you're talking about, but I'm not doing that.
uh ?... then what's the point ?
To put it simply, I am not interested in the game side of EteRNA. Making a bot to solve puzzles and reaching the top of the ranking list looks very vain to me. Besides, UCT is probably one of the absolute wrongest choice for that job (not going to explain why here, watch the vid linked above, and try to figure that out for yourself). I'm here for the science, and I'm trying to learn in the first place, and to build tools that will help me (and hopefully others) with the science, the lab experiments. But, just like the puzzles represent an excellent training ground for EteRNA players, to make them qualified EteRNA scientists if you will, they are also a very good test for a bot. If a software can compare to humans in the game, and by that, I mean achieve decent results while respecting the same rules, then it is a good sign. Well, I hope so...
yeah, but the current bot's rank...
... is nothing more than the proof that any human player with :
- half a brain
- a huge amount of free time
- and no fear of carpal tunnel
can easily make 400'000 points in the game with the current puzzle database.
Does the bot solve switches ?
Yes. It should be noted though that its current performance is not on par with what it's capable of with single-shape puzzles.
Will the bot be available in the upcoming scripting interface ?
It could, provided EteRNA would make the required Vienna APIs available. Currently, it doesn't seem possible (the bot needs to do constrained folds and also to compute the energy of given structures, the Lib.fold() API function is just not enough)
How come its submitted lab designs don't even fold properly ?
For puzzle solving, I'm using Vienna 2.1.1 with older imported parameters from version 1.8.5, so the results are pretty close but still not always exactly like EteRNA predicts. When working in lab mode, I'm using 2.1.1 with no specific parameters (for now), which means that predictions can vary more widely (more details in this document). I chose to run the bot with the latest version because I'm assuming that they made some progress with the models they're using, and I'd be curious to test this hypothesis.
Things that went through my head while I was building Vinnie :
"Now I understand why no one else has tried bothering about writing a puzzle solver that would respect ALL the rules (max GC, min GU, etc)"
"Mismatching is just as important as proper matching, though it's far more subtle !"
"Surprisingly (or perhaps not), it's actually terribly difficult to make the absolute best choice out of countless perfect ones"
"A puzzle to remember, 15837... Not a tough one, but it took me 2 days to figure out why the engine would systematically fail (time-out) on that one. Everything would go smooth until it reached about 2/3 of the molecule. Then, the stalling. The engine would not find a way to go past that point... Long debugging, before I finally realized that the data coming from the web server was including something peculiar : a pseudoknot... (-_-) "
"After a few hours of C/C++ 'surgery' on a program, taking a few steps back and watching the 'thing' from a distance, it's actually quite amazing how much insight you can get into what it could have meant to be Dr. Frankenstein..."
"Interestingly, it is in fact equally important to determine what is important and what is not"
|<img src="http://imgs.xkcd.com/comics/the_general_problem.png" alt="" />|
|(credits are almost unnecessary, but yes, this was stolen from xkcd)|
How it all began
On October 31st 2012, an important meeting took place in the chat. It would be followed by regularly spaced dev chats, as we know them. That day, Rhiju Das was present.
rhiju: to solve switch puzzles, do you thnk it will be possible to collate a bunch of 'features' of good switch designs? [6:10 PM]
rhiju: or do we need something lke jieux's strategy, which is more like a full protocol or 'recipe' [6:10 PM]
rhiju: maybe we can break this into 2 questions [6:11 PM]
rhiju: there are actually two 'fronts' on switches [6:12 PM]
rhiju: in one 'front', there's the question of why switches that 'work' in siiico, don't work as well in real life [6:13 PM]
rhiju: that's analogous to what we tried to solve for non-switch puzzles [6:13 PM]
rhiju: and there we got an impressive list of features that players 'saw' in designs that 'worked' expeimentally [6:13 PM]
rhiju: so one question is wlll we be able to apply the same 'strategy market' idea [6:14 PM]
rhiju: a second 'front' (coming soon) is a purely in silico question [6:14 PM]
rhiju: there are no algorithms to really effectively solve switch puzzles that involve transitions between more than two states [6:14 PM]
rhiju: for example, now we have +/- FMN. we can also create puzzles with four states, and you would be asked o toggle between them by adding FMN or not, and by adding theophylline or not (4 conditions) [6:15 PM]
jnicol: are these modeled off what nature currently does, or we think it does? [6:17 PM]
jnicol: and is a 3 state switch useful in nature? [6:17 PM]
rhiju: @jnicol, there are some natural RNA switches that have different functions depending on the presence or abence of mre than one small molecule [6:18 PM]
rhiju: Some are called 'tandem riboswitches' [6:18 PM]
rhiju: ANd moreoever, many engineers are trying to make RNA switches that turn on or off only when they see molecules X, Y, and Z [6:19 PM]
rhiju: Folks at caltech and MIT. One application is in 'gene therapy', where you ask a gene to be delirvered only to cells that are expressing the right four other mRNAs [6:20 PM]
Call me crazy, but those two lines were the trigger. One hell of a challenge, for sure, but I wanted to see if I could come up with something... I'm still unsure whether it was worth the effort, and whether anything substantial will ever come out of it, but I won't regret the time spent. If nothing else, I already learned a lot.