Kрайното класиране на финалния кръг
Категория: Интернет
неделя, 10 Февруари 2002 0:00ч
Задачата, избрана за финалния кръг, известна в литературата като Ривърс (от англ. reverse, обърни) е била много популярна в Англия през XIX век. Най-малко двама души, живели тогава, претендирали да са нейни създатели. Всеки един от тях имал разработено собствено ръководство за игра и школа за подготовка на състезатели. Играта е имала огромен успех по това време. Всъщност по всичко изглежда, че това е една много стара игра, преоткривана многократно през поколение. Така става и през 70-те години на миналия век, когато играта отново излиза на мода и се разпространява под името Отело. Днес някои от производителите на мобилни телефони включват играта в произвежданите от тях апарати.
За съжаление (или за щастие) при тази игра не е известна проста печеливша стратегия за никой от играчите. Един от корифеите на занимателната математика М. Гарднер отделя подобаващото се място на Ривърс в своя знаменит труд “Математически развлечения” (изд. Наука и изкуство, София, 1977г.). Една от предлаганите в книгата на Гарднер тактики се състои в това играчът да се стреми да прави ходове в рамките на колкото може по-малък квадрат, разположен в центъра на игралното поле. С помощта на компютрите се откриват нови възможности за анализиране на играта, за търсене на стратегии и т.н.
Ето и коментара на самия победител за реализираното от него решение на задачата: “Стандартното решение на този тип задачи (в които се търси оптимална стратегия за игра, в която двама играчи правят ходове един след друг) е т.н. минимаксен алгоритъм. За целта се дефинира функция, която връща някаква стойност, свързана с резултата от играта. Функцията, която аз използвам, връща разликата между броя на пуловете на всеки от двамата играчи, взета със знак плюс, когато трябва да избера ход като първия играч и със знак минус, когато трябва да избера ход като втори играч. Естествено първият играч иска да максимизира печалбата си, а вторият - да я минимизира (т.е. да максимизира своята). Алгоритъмът построява класическо минимаксно дърво на играта, като проверява всички възможни ходове на всеки от играчите и се опитва да намери този от своите ходове, при които минимизираща стратегия на противника ще го доведе до позиция с максимална възможна печалба (или минимална загуба, ако не е възможно да се спечели). Разбира се, не е възможно да се построи пълното минимаксно дърво на играта, което е много голямо. Затова строя дървото от текущата позиция с дълбочина 5, защото при тази дълбочина времето от 1 секунда е достатъчно да се проверят всички ходове.”
С оглед на ограниченото време за работа на програмите беше добре всеки от състезателите да реализира бързо някой не много сложен, но сигурен (не правещ грешни ходове) алгоритъм. Фаворит на журито е greedy алгоритъмът, наречен условно best-local, който избира от всички възможни поставяния на текущия ход това, което дава най-добър резултат.
На сайта на конкурса (www.konkurs.musala.com) можете да намерите решенията на всички финалисти и тестовата среда. Предлагаме на любопитните читатели да създадат свои програми и да премерят сили с решенията на финалистите (направени за 5 часа).
