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

Задача 4 от брой 01/2006 - ВМЪКНИ - Анализ


Задача четири от нашия конкурс за трета поредна година акцентира върху Microsoft технологиите, като същевременно предложи на участниците възможност да премерят сили в писането на компютърни играчи за една интересна и нестандартна игра. Това от своя страна означаваше, че могат да бъдат реализирани много идеи и стратегии, които са полезни в различни ситуации.

Важна особеност при оценяването при тази игра е че крайното класиране се базира на точките, които са спечелени по време на всички игри. Колко победи е спечелило едно решение не указва директно влияние върху резултатите. Ето защо едно решение, което играе с цел да отбелязва максимално количество точки без да се интересува от точките на противника би могло да постигне добър резултат. От друга страна е важно да се играе така, че противника да получава колкото се може по-малко точки. Добра стратегия, която използват някои от участниците, е да се следи поведението на противника. Ако опонента играе с цел винаги да получава максималните точки за ход следва, че той се интересува главно от спечелените точки. Възможно е противниковото решение да играе за победа и да се опитва винаги да отбелязва повече точки от опонента си. С известна точност може да се определи какво е поведението на противника в една игра и да се действа по различен начин спрямо него. Една добра оптимизация е да се следи дали противника не играе постоянно ход номер 6, който се играе служебно, когато едно решение превиши позволеното времево ограничение. Ако са изиграни последователно няколкото такива хода може да се приеме, че решението ще играе служебно този ход до края. Това би позволило да се спечелят повече точки срещу съответния противник.

Един стандартен подход, който се използва за подобни игри е принципа на минимума и максимума. Ситуациите, които се появяват в една игра се оценяват и в дадена ситуация се играе най-добрият ход спрямо тази оценка. Разбира се оценката може да бъде различна и зависи от стратегията за игра на дадената програма. Този подход не е добър при игри с голям брой ситуации, както е в тази задача. Ето защо може да се използва подхода на алфа-бета отсичането. При него не се разглеждат всички ситуации, а само тези, които са перспективни. Разбира се това обхождане може да се ограничи до няколко хода дълбочина, за да работи достатъчно бързо. Повече информация за алфа-бета отсичането може да намерите на сайта на конкурса в анализа на задача 5 от 2003 година.

Този подход може да се развие дори още повече като се използва така нареченото Iterative Deepening търсене. Този вид търсене протича на стъпки. В първата стъпка се прави обхождане, ограничено до някаква дълбочина. На следващата стъпка обхождането се прави до дълбочина с 1 по-голяма от тази на предната стъпка. Това се прави докато не е изтекло времевото ограничение. За да се подобрят получените резултати на дадена стъпка от търсенето може да се използват резултатите намерени на предишната. С тяхна помощ може да се избере в какъв ред да се проверят възможните ситуации, като се има предвид получената за тях оценка на предишната стъпка и първо се преглеждат ситуациите с по-добра оценка. Важно е каква оценка да се избере. Участникът в конкурса Васил Поповски е избрал оценка, чрез която се стреми да има по-добър резултат от противника си, а при равен резултат да максимизира собствените си точки. Като се прилага  Iterative Deepening търсене се използва по-добре позволеното за работа време, тъй като се правят обхождания с все по-голяма дълбочина и когато времето свърши се спира и се взема най-добрият получен резултат.


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

Supported by Musala Soft Ltd.

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