Фиг.1

За съжаление нашите програми, за разлика от тестващата програма, не притежаваха способността да предвиждат бъдещето. Тестващата програма, въпреки че притежаваше такава способност, просто не се интересуваше от оптималните стратегии. След като аз я подправих малко, тя успя да произведе евентуалните резултати при използването на гореописаната оптимална стратегия. Резултатите бяха просто фантастични за всичките тестове, освен 4, 7 и 8. Обаче за тези резултати -- по-късно.

2. Стратегия, която аз използвах в "release" версията.

Въпреки че гореописаната оптимална стратегия не е приложима в реалните програми (освен ако РС-то няма чип, предсказващ бъдещето :), тя дава ориентир за създаване на една реална проста стратегия. Тя е следната: Вярно е, че аз не мога, намирайки се в дадена точка, да определя, дали тя е локален максимум или минимум (за целта аз трябва и да знам величината на фиксинга в следващата точка, т.е. на следващия ден в нашата виртуална реалност). Обаче аз мога да видя дали предишната точка не е локален екстремум. Ако е -- произвеждам съответната покупка/продажба на долари, макар и с малко закъснение. Ако ли не -- не правя нищо. Ако фиксингът се мени сравнително плавно, и, освен това, броят на точките между точките на локалния екстремум не е прекалено малко, тази стратегия би трябвало да даде нелоши резултати. Тъкмо тази стратегия аз използвах в "release" версията на програмата, без никакви други хитрини.

3. Подобрена стратегия с усредняване.

Гореописаната стратегия ще се издъни яко, ако локалните екстремуми са разположени толкова нагъсто, че неекстремални точки почти или изобщо няма. Виж следната рисунка ("трион"):

Причината за това пропадане е очевидна: нашите "ходове" ще са в противофаза с това, което реално трябва да се направи (купуване на долари вместо тяхната продажба и обратно). Това довежда до експоненциално намаляване на първоначалния ресурс (доларовия еквивалент на 1 000 000 лева), вместо до неговия експоненциален ръст. Разбира се, такова поведение на фиксинга едва ли се среща в реалния живот, обаче малки флуктуации с "трионообразен" характер, наложени върху "по-гладка" бавноизменяща се функция, са доста по-реалистични:

Фиг.3

Един от начините да се неутрализира влиянието на такива малки флуктуации е усредняването на фиксинга по няколко съседни точки (нещо като "antialiasing", т.е. изглаждане на флуктуациите). В борсови термини това ще е аналогично на заемане на "дълги доларови (или левови) позиции".

По този начин ние игнорираме голяма част от "високочестотните" труднопредсказуеми екстремуми, обаче няма да пропускаме точки в околността на стабилните "нискочестотните" такива (зелените точки на Фиг.3). Очевиден недостатък на този метод е, че евентуално се пропуска голям брой възможности да се увеличи капиталът. От друга страна пък вероятността на експоненциални загуби в дълги трионообразни поредици от локални екстремуми се намалява значително.

Този вариант аз го реализирах в програмата, обаче за мое нещастие малко преди края на състезанието открих един бъг, който така и не успях да изчистя до последните секунди. По-късно се оказа, че този бъг е фантомен (сигурно е артефакт на debugger на VC++6), защото аз не успях да го възпроизведа в спокойна обстановка. Обаче заради този привиждащ ми се бъг аз приех решение да компилирам в окончателната версия само по-простичък вариант, без усредняване по малките флуктуации. И това решение се оказа фатално.

4. Резултати от тестовете при използване на усредняването.

Когато тестовете се появиха на сайта, аз веднага пуснах версията с усредняването, за да видя какви биха били резултатите, ако бих поел риска да пусна по-добър вариант, игнорирайки привидните бъгове.

За целта аз смених само два байта в сорса (променяйки броя на точките, върху които фиксинга се осреднява, от 1 (няма осредняване) на 3 и заменяйки в сорса #if 1 на #if 0). За всички тестове освен 3 и 5 качествена разлика в резултатите на конкурсната версия и версията с усредняванията нямаше. Обаче резултатът от 3 тест беше направо фантастичен: над 2.4 милиарда $$!!! Петият тест не беше толкова впечатляващ: "само" 233 милиона $$.

ОК. А какво ще стане, ако броят на точките по които усреднявам, стане, да речем, 2, а не 3? В този случай тест 3 дава малко под 2 милиарда, а тест 5 -- съвсем скромните 23 милиона. И при други значения на този параметър (4 или 5) резултатите са по-лоши, отколкото при усредняване по 3 точки. Всичко това е много хубаво, обаче 2 милиарда -- това е прекалено близо към горната граница за int. Ако РС-то на журито беше малко по-бързо от моето, тази граница лесно би могла да се прескочи, и тогава би станала голяма каша (поява на големи отрицателни стойности в тестовите резултати). Защото се оказа, че в тестващата програма, както и в моята, подобна възможност изобщо не е била предвидена. Между другото, това явление се наблюдаваше и на моето РС, когато изключих debug опцията TEST на препроцесора. Тази опция пишеше много тъпотийки по екрана, за сметка на което програмата "трупаше пари" по-малко време, отколкото би могла в противен случай. В тарапаната на последните секунди на финала аз чисто и просто забравих да я изключа. За да елиминира евентуалното влияние на "int range owerflow" бъг, аз замених както в моята, така и в тестващата програма int на _int64 за описване на доларови наличности. След което пуснах тестовете още веднъж. Резултатите за третия тест (единствения, който би могъл да бъде засегнат от бъга) се оказаха още по-впечатляващи: при усредняване по 3 точки програмата натрупа над 14 милиарда $$!!!!!, докато при усредняване по 2 точки -- 3 милиарда. Който не вярва, може да изтегли 64-битови версии на deal.exe и timer.exe за да провери; точният брой милиарди ще варира, разбира се, в зависимост от бързината на вашето РС.

4. Горните граници за възможните печалби.

Най-накрая помествам, както обещах, и най-добрите теоретично възможни резултати за всичките тестове.

Както се вижда от таблицата, и при "реалистичен" фиксинг от Тест 4 е възможно, теоретично поне, да се спечелят близо 40 милиона долара. Тъй че проблемът за написване на умна програма, която ще може да изкара поне 10 милиона от тези 40, е наистина много интересен. Ако някой напише подобна програма, той сигурно може да стане милионер. Ако не от игра на борса, то от продажбата на програмата :). И аз имам след финала някои идеи в тази насока, и ще се опитам да ги реализирам, за да видя, дали наистина струват :)).

Една от тези нови стратегии -- а, по-точно, модификация, която може да се приложи към всяка стратегия -- ще я опиша сега.

5. Използване на "огледална" стратегия.

Тази стратегия се основава на следното наблюдение върху моите аномални резултати от тестовете 1,2 и 6: използваната стратегия доведе до експоненциално намаляване на първоначалния ресурс, което значи, че в тези тестове имаше много трионообразни локални екстремуми (като на рисунките 2 и 3 горе). Т.е. аз бих получил експоненциално растящи суми, ако бях използвал стратегия, обратна на тази, която използвах реално (т.е. бях купувал долари там, където оригиналната стратегия ги продава и обратно). Обаче, ако бих използвал само обратната стратегия, то бих се провалил в 3 и 5 тест.

Какво да правим, ако не знаем предварително поведението на фиксингите в дадения тест? Ами много просто: разделяме първоначалната сума на две равни части от по 500 000 лева, като с първата половина играем по оригиналната стратегия (каквато и да е тя), а с другата -- по обратната. Тогава при всички тестове (освен 4, 7 и 8) аз би трябвало да имам многомилионни печалби (при стратегия с усредняване). Като, разбира се, печалбата при тестовете 3 и 5 би трябвало да е примерно 2 пъти по-малка, отколкото при използване само на първоначалната стратегия. Това е цената на смесената стратегия. А цялата тази смесена стратегия произлиза от неравенството 1/2(x + 1/x)>=1 (за x>0). Резултатите от тестовете потвърждават тези изводи.

За тези тестове (а и за по-нататъшните експерименти със различните стратегии) аз превърнах тестващата програма timer.exe в една динамична библиотека (fixings.dll) с цел нейната комуникацията с deal.exe да става по много по-бърз и естествен начин, без хилядократното извикване на deal.exe и писане във различни файлове. Fixings.dll и модифицираната deal.exe (заедно със съответните сорсове и batch файлове runalltests.bat и runtest.bat, позволяващи всички осем теста да извървят мигновено, за части от секунда), може да бъдат изтеглени оттук.

Batch файл runalltests.bat произвежда 16 подробни .log файла (по 2 файла за всеки тест #N: dealN.log (за обичайна стратегия) и dealNs1.log (за "двойна" стратегия)). В реда Т на всеки файл са посочени резултатите на играта след момент (или "ден") Т, като числото в последната колона е сума от левовите и доларовите наличности, изразена през долари (по текущ фиксинг). От тези логфайлове може да се види, че резултатите от тестовете 1, 3 и 6 с използването на огледалната стратегия биха били над 7 милиона, 19 милиона и 9 милиона долара съответно. При Т в околността на 1700, докъдето тестовете на финала реално вървяха, иначе милионите при Т==2000 са доста повече. За сметка на това пък в теста 3 биха намалели милиардите, тъй че сумарно, по всичките тестове, стратегията с усредняване + огледална стратегия би се проявила по-лошо, отколкото "чиста" стратегия с усредняване. Обаче в реалния живот почти всеки би предпочел стратегия, която с равна вероятност осигурява или печалба от 5 милиарда или запазване на "последния милион", пред стратегия, която при успех ще донесе 10 милиарда, а при провал ще доведе до загуба на този последен милион. Думата "последен" тук е много важна, тъй че всичко това не се отнася, да речем, за Джордж Сорос :). А и за повечето българи, руснаци (че дори и американци :)) горните алтернативи са, разбира се, извън техния "реален живот", освен ако не са мащабирани така, че "последния милион" се свежда до "последната хилядарка" или "последните 100 лева/долара".