* Fcrack v1.0 Fcrack is a set of tools to find out the secret -F number used on KOTH servers such as Pizza and KOTH.org. It is an optimised brute force method that simulates battles to find the -F number. It can easily search the entire 2^31 sized key space of pmars 0.9.2. Report bugs and/or suggestions to jpihlaja@cc.helsinki.fi * Compiling the sources On Unix typing `make' in the `src' directory should build the following executables in the toplevel directory: mkmap -- Utility to create Win/Loss/Tie maps for every possible starting position and a pair of warriors. mapsim -- Fast simulator of battles using the W/L/T maps created by mkmap. flipmap -- Create a 'B vs. A' map from a 'A vs. B' map (see the section on mkmap below). Fcrack -- Dumb Brute Force search for -F numbers. You may see some warnings about signed vs. unsigned comparisons but they can be safely ignored (they are from exhaust's code and I wasn't bothered enough to fix it). See the relevant sections on each utility below following the quick start for more information and the subtleties involved in the search. ----------------------------------------------------------------- * What is an -F number? The -F switch in pmars is used to seed the random number generator that it uses to compute the loading distance of the second warrior from the first when fighting a round. Oh, nevermind... from the pmars man page: -F # This option tells the loader to install warrior 2 at a fixed address # for round 1. This number is then used to seed the pseudo random number genera- tor for all subsequent warriors and subsequent rounds. This option is useful for testing differ- ent versions of a warrior with constant initial placement. Warrior 1 is always installed at address 0. Why is it useful? Well, if you know where your opponent is going to be loaded the next round, you can kill him easily and surely. But that's highly unethical and only really possible with p-space so you shouldn't do that. Another possibility is to optimise your quickscan for that specific positioning sequence -- perhaps to win against other warriors or gain points in self-fights. It goes without saying that those too are bubuus. Note that most hill servers change their -F numbers monthly, so -F number optimisation would only give you short-time benefit. Besides, local optimisation like that isn't necessarily good for your warrior's life-expectancy. ----------------------------------------------------------------- * Quickstart There are three phases to finding the -F number: probing the hill, precalculation of some tables, and the brute force search for the -F number. For concreteness' sake, assume that the secret -F number is 4000. 1) Probing the hill You need to have the source to three or four different warriors. If the hill doesn't use self-fights one of the warriors needs to be on the hill. Now submit the others and write down their score lines. For example, you have Aeka on the hill and you submit Rave and Flash Paper 3.7 and get the following results: W L T Aeka vs. Rave 125 64 11 Aeka vs. Flash Paper 4 4 192 where Wins are reported for Aeka and Losses for the challenger. (These were obtained from running pmars with the -F 4000 -r 200 like so: pmars -br 200 -F 4000 Aeka.red Rave.red.) 2) Preparing the Win/Loss/Tie maps The brute force search uses precalculated tables to speed up it's search, called `maps'. For two warriors A and B all possible rounds are fought between them and recorded in a table. You need to create tables for each pair of warriors whose score line you gathered in the prevoius phase. You do this with the `mkmap' utility. To create the map of warrior A vs warrior B into a file `A_vs_B.map' type: $ ./mkmap [options] A.rc B.rc >A_vs_B.map where the options are the same that the exhaust and pmars simulator accept for specifying the environment. In our example we have the score lines for Aeka vs. Rave, and Aeka vs. Flash Paper so we create those maps: $ ./mkmap aeka.rc rave.rc >aeka_vs_rave.map $ ./mkmap aeka.rc flashpaper.rc >aeka_vs_flashpaper.map This could take a while to compute for each map as it needs to fight about 16000 rounds for each map (assuming a normal hill environment). If it's taking too long you should give the '-v' flag to mkmap to get periodic progress reports every five seconds on the screen. You should know that an 'A vs. B' map is different from a 'B vs. A' map, although they are related. 3) The search phase Ok, now you have all the information needed to start the search. The synopsis of the Fcrack command is: $ ./Fcrack [options] [mapfile win-loss-tie]... See the section on Fcrack below or run Fcrack with the -h flag for info about the options. Enter the three score lines found in the first step as follows: $ ./Fcrack aeka_vs_rave.map 125-64-11 aeka_vs_flashpaper.map 4-4-192 4000 The program outputs 4000, the correct -F number. Note that none of the score lines alone is enough to find the -F number uniquely (try it by deleting two), but needs at least one other. This simple example only needs two w/l/t results, but for the full space search you may need as many as five or six. Please read the detailed description if you are having trouble since the process depends heavily on the hill server's setup. ----------------------------------------------------------------- * Programs * exhaust -- see exhaust's README in the src/ subdirectory and the manual that comes with pmars. * mkmap -- creates a map files Synopsis: mkmap [-a seconds] [-c cycles] [-s coresize] [-p maxprocesses] [-d minsep] [-v] warrior1.rc [warrior2.rc] Options: -a # Sets the progress report alarm interval to # seconds. Used with -v. -c # Set cycles until tie limit = # cycles. -s # Set coresize to # cells. -p # Set max. processes to # processes. -d # Set minimum warrior separation to # cells. -v Be verbose -- outputs progress reports every so often (default 5 seconds) as a fraction A/B tending to 1. Description: This program computes every possible one round battle between a pair of warriors A and B and outputs the result to the standard output. There are 2*(CORESIZE+1 - 2*MINSEP) such battles for two distinct warriors A and B: in half of them A starts first and in the other B starts first. If you specify only one warrior on the command line then the map for self-fights for that warrior is computed. This needs to compute only half as many battles as for a full map. The map itself can be quite enlightening with it's patterns. Here's an example map for Flash Paper vs. Rave in a minicore of size 378: # minsep: 100 # npos: 179 # evens +++++++++--++--.-++-.+++++..+++++.+.++-----+++--.-.-.+-+---- --+-----.+--++++++++++++++.+----------.+...+..++++-+-++.+.++ ++.-+-+-----------+++++++++++++++++++++++++------++++++---- # odds +++++++++--++--.-++-.+++-+..+++-+.+.++-----+-+--.-.-++-+---- --+-----.+--+++++++++++-++++----------.+.+-+..+++.-+-++.+.++ +-.-+-+-----------++++++++++++++++++++++++-------++++++---- Lines starting with '#' are comments except for the two first ones specifying the minimum separation and number of possible loading distances for the second warrior (Rave). The 'evens' half of the map corresponds to the even cycles of a battle (when Flash Paper executes first) and the 'odds' half to the odd cycles (when Rave executes first). Plus (+) characters represent Flash Paper's victories and minuses (-) Rave's victories with dots (.) standing for ties. * flipmap -- flip the orientation of a map file Synopsis: flipmap mapfile Description: Computes the mapfile for B vs. A from a map file of A vs. B. Both Fcrack and mapsim take an -x option and do it by themselves, so this isn't really needed unless you want the maps for themselves. * mapsim -- simulate battles quickly using a precomputed map Synopsis: mapsim [-r rounds] [-k] [-F seed] [-x] mapfile Options: -r # Set the number of rounds to play. -F # Seed the RNG (initial position of warrior #2). -k koth output format. -x flip the orientation of mapfile before playing. Description: This utility can quickly compute the results of a battle given a map file. It is mainly for testing purposes, but may be useful. E.g. $ mapsim -F 4000 -r 10000 aeka_rave.map Results: 2325 1387 288 * Fcrack -- search for an -F number satisfying some W/L/T constraints Synopsis: Fcrack [-a seconds] [-i low-F high-F] [-chvx] [mapfile wins-losses-ties]... Options: -a # Set the progress report interval to # seconds (default 20). Used with -v. -c Search the complete search space. Faster than linearly searching the entire search space using -i. -i LO HI Sets the interval to be checked to LO <= F < HI. The default is to check the valid range of load positions of the first mapfile. This interval is checked linearly from LO LO+1 ... Hi-1. -h Prints a help text. -v Be verbose. This prints a progress line of the search and echoes found -F number candidates to standard error every so often (controlled by the -a option). -x Flips the mapfiles before the search. Useful if you don't know whether the server runs the challenger on odd or even rounds. Description: Given some win/loss/tie statistics of some battles Fcrack computes the set of -F numbers that satisfy those constraints. It can test -F numbers in a given interval, or search the full space of -F numbers for candidates using an optimised algorithm. The brute force idea is to simulate for each possible -F number the outcome of the battle using a cached file of results and compare the result against the Win/Loss/Tie constraint given on the command line. If the results match for each constraint, then the -F number is output. With enough constraints the secret -F number can be recovered. Normally, the program checks each -F number in an interval one by one. If the -c flag is given, it tests all of the -F numbers in the search space in a non-linear fashion: f(S), f(f(S)), f(f(f(S)),... where S is any initial seed and f is the pseudo random number generator used to compute warrior load distances. The constraints (the mapfile and w/l/t result) are tested in the order they are given on the command line. Hence, the order affects the runtime of the program. You should attempt to sort the constraints by increasing probability. e.g. If your scanner is expected to score 50/50/0 against another scanner and on the hill it really scores 80/20/0, then you should definitely put that constraint first. While not an issue for a small interval search, the full space search can benefit from proper ordering of constraints.