Състезателна система | ||||||||||||||
|
Задача 4 от брой 01/2006 - ВМЪКНИ - Анализ Задача четири от нашия конкурс
за трета поредна година акцентира върху Microsoft технологиите, като същевременно предложи на участниците
възможност да премерят сили в писането на компютърни играчи за една интересна и
нестандартна игра. Това от своя страна означаваше, че могат да бъдат
реализирани много идеи и стратегии, които са полезни в различни ситуации. Важна особеност при
оценяването при тази игра е че крайното класиране се базира на точките, които
са спечелени по време на всички игри. Колко победи е спечелило едно решение не
указва директно влияние върху резултатите. Ето защо едно решение, което играе с
цел да отбелязва максимално количество точки без да се интересува от точките на
противника би могло да постигне добър резултат. От друга страна е важно да се
играе така, че противника да получава колкото се може по-малко точки. Добра
стратегия, която използват някои от участниците, е да се следи поведението на
противника. Ако опонента играе с цел винаги да получава максималните точки за
ход следва, че той се интересува главно от спечелените точки. Възможно е
противниковото решение да играе за победа и да се опитва винаги да отбелязва
повече точки от опонента си. С известна точност може да се определи какво е
поведението на противника в една игра и да се действа по различен начин спрямо
него. Една добра оптимизация е да се следи дали противника не играе постоянно
ход номер 6, който се играе служебно, когато едно решение превиши позволеното
времево ограничение. Ако са изиграни последователно няколкото такива хода може
да се приеме, че решението ще играе служебно този ход до края. Това би
позволило да се спечелят повече точки срещу съответния противник. Един стандартен подход, който
се използва за подобни игри е принципа на минимума и максимума. Ситуациите,
които се появяват в една игра се оценяват и в дадена ситуация се играе
най-добрият ход спрямо тази оценка. Разбира се оценката може да бъде различна и
зависи от стратегията за игра на дадената програма. Този подход не е добър при
игри с голям брой ситуации, както е в тази задача. Ето защо може да се използва
подхода на алфа-бета отсичането. При него не се
разглеждат всички ситуации, а само тези, които са перспективни. Разбира се това
обхождане може да се ограничи до няколко хода дълбочина, за да работи
достатъчно бързо. Повече информация за алфа-бета
отсичането може да намерите на сайта на конкурса в анализа на задача 5 от 2003
година. Този подход може да се развие
дори още повече като се използва така нареченото Iterative Deepening търсене. Този вид търсене протича на стъпки. В първата
стъпка се прави обхождане, ограничено до някаква дълбочина. На следващата
стъпка обхождането се прави до дълбочина с 1 по-голяма от тази на предната
стъпка. Това се прави докато не е изтекло времевото ограничение. За да се
подобрят получените резултати на дадена стъпка от търсенето може да се
използват резултатите намерени на предишната. С тяхна помощ може да се избере в
какъв ред да се проверят възможните ситуации, като се има предвид получената за
тях оценка на предишната стъпка и първо се преглеждат ситуациите с по-добра
оценка. Важно е каква оценка да се избере. Участникът в конкурса Васил Поповски
е избрал оценка, чрез която се стреми да има по-добър резултат от противника
си, а при равен резултат да максимизира собствените
си точки. Като се прилага Iterative Deepening търсене се използва по-добре позволеното за работа
време, тъй като се правят обхождания с все по-голяма дълбочина и когато времето
свърши се спира и се взема най-добрият получен резултат. За въпроси можете да ни пишете на адрес: konkurs@musala.com. Copyright 2000-2010 by Musala Soft Ltd. All rights reserved. |