Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Сезон 2001 - 2002
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2000 - 2001
Финален кръг

На 8.05.2002г. се проведе Финалният кръг на Осмия Конкурс по програмиране на PC Magazine и Мусала Софт. Програмата на състезателния ден и правилата провеждане финалния кръг можете да свалите от тук (RTF Format).

Тази година шестте задочни кръга на Конкурса привлякоха рекорден брой участници - 117 души изпратиха решение на поне една от задачите на Конкурса (а те не бяха никак лесни). От всички участници 21 изпратиха решения на всички предложени задачи. Най-добрите 12 участници от задочните кръгове, сред които бяха 5 от 6-те победители, се срещнаха на Финала. За този решителен етап на Конкурса (да припомним че резултатите от задочните кръгове не влияят на класирането от Финала) журито избра следната задача (RTF Format).

Програмите на 12-те участника бяха “изправени” една срещу друга в турнир по системата “всеки срещу всеки” в дава мача - веднъж от позицията на играч А, веднъж от позицията на играч В. Ето резултатите от този драматичен сблъсък:

vs. 01 02 03 04 05 06 07 08 09 10 11 12
01 0 -30 30 30 30 27 8 -30 30 24 30 -19
02 30 0 30 30 30 27 -21 30 30 25 30 -32
03 30 -30 0 30 30 13 -18 30 30 -30 30 -8
04 -30 -30 -30 0 -30 -30 -30 -30 -30 -30 -30 -30
05 -30 -30 -30 -30 0 -30 -30 -30 -30 -30 -30 -30
06 30 -40 30 30 30 0 -30 -18 -28 -40 -54 -41
07 30 3 30 30 30 32 0 -18 30 4 30 -44
08 -12 -34 30 30 30 -30 -12 0 30 2 30 -30
09 13 -28 30 30 30 13 30 30 0 2 30 31
10 31 48 30 30 30 46 -4 -42 -44 0 30 -32
11 -30 -30 -30 -30 -30 -30 -30 -30 -30 -30 0 -30
12 13 -4 30 30 30 13 7 30 30 24 30 0


Съгласно регламента тези резултати оформиха и крайното класиране на Финалния кръг:

Place Name No.ID Points A Points B Points Diff A Diff B Diff
1 Петко Минков 12 30 30 60 233 265 498
2 Янислав Янков 02 27 27 54 209 205 414
3 Трифон Трифонов 07 27 24 51 157 130 287
4 Иван Станишев 09 30 15 45 211 -18 193
5 Андрей Николов 08 18 21 39 34 78 112
6 Валентин Цеков 10 21 15 36 123 79 202
7 Николай Тодоров 01 24 12 36 130 -75 55
8 Николай Чилев 03 21 9 30 107 -150 -43
9 Милослав Средков 06 12 12 24 -131 -51 -182
10 Мартин Чилев 11 0 9 9 -330 -126 -456
11 Владимир Молотков 04 0 6 6 -330 -210 -540
11 Камен Добрев 05 0 6 6 -330 -210 -540


За втори пореден път победител във финалния кръг е Петко Минков (Пловдив), а на второ място е победителят от задочната част на Конкурса - тази година това е Янислав Янков (В.Търново).

Задачата избрана за Финалния кръг, известна в литературата като Ривърс (от англ. reverse, обърни) е била много популярна в Англия през XIX век. Най-малко двама души, живели тогава, претендирали да са нейни създатели. Всеки един от тях имал разработено собствено ръководство за игра и школа за подготовка на състезатели. Играта е имала огромен успех по това време. Всъщност по всичко изглежда, че това е една много стара игра “преоткривана” многократно през поколение. Така става и през 70-те години на миналия век, когато играта отново излиза на мода и се разпространява под името Отело. Днес някои от производителите на мобилни телефони включват играта в произвежданите от тях апарати.

За съжаление (или за щастие) при тази игра не е известна проста печеливша стратегия за никой от играчите. Един от корифеите на занимателната математика М. Гарднер отделя подобаващото се място на Ривърс в своя знаменит труд “Математически развлечения” (изд. Наука и изкуство, София, 1977г.). Една от предлаганите в книгата на Гарднер тактики се състои в това, играчът да се стреми да прави ходове в рамките на колкото може по-малък квадрат, разположен в центъра на игралното поле. С помощта на компютрите се откриват нови възможности за анализиране на играта, за търсене на стратегии и т.н.

Ето и коментара на самия победител за реализираното от него решение на задачата: “Стандартното решение на този тип задачи (в които се търси оптимална стратегия за игра, в която двама играчи правят ходове един след друг) е т.н. минимаксен алгоритъм. За целта се дефинира функция, която връща някаква стойност, свързана с резултата от играта. Функцията, която аз използвам връща разликата между броя на пуловете на всеки от двамата играчи, взета със знак плюс, когато трябва да избера ход като първия играч и със знак минус, когато трябва да избера ход като втори играч. Естествено първият играч иска да максимизира печалбата си, а втория - да я минимизира (т.е. да максимизира своята). Алгоритъмът построява класическо минимаксно дърво на играта, като проверява всички възможни ходове на всеки от играчите и се опитва да намери този от своите ходове, при които минимизираща стратегия на противника ще го доведе до позиция с максимална възможна печалба (или минимална загуба, ако не е възможно да се спечели). Разбира се не е възможно да се построи пълното минимаксно дърво на играта, което е много голямо. Затова строя дървото от текущата позиция с дълбочина 5, защото при тази дълбочина времето от 1 секунда е достатъчно да се проверят всички ходове.”

С оглед на ограниченото време за работа на програмите беше добре всеки от състезателите да реализира бързо някой не много сложен, но сигурен (не правещ грешни ходове) алгоритъм. Фаворит на журито е greedy алгоритъмът наречен условно best-local, които избира от всички възможни поставяния на текущия ход това, което дава най-добър резултат.

Предлагаме на любопитните читатели да създадат свои програми и да премерят сили с решенията на финалистите (направени за 5 часа). Средата за тестване можете да намерите тук.


Мечо Пух - героят на нашата задача ;-)


Във фото галерията можете да намерите снимки от създаването на задачата, състезанието и награждаването.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.