Задача 5 от брой 02/2004 - Е-ХО - Анализ

Задачата от Петия кръг на нашия Конкурс беше избрана при наличието на една допълнителна цел. Тази цел беше да привлечем вниманието на участниците към платформата .NET.  Решихме, че най-добре същността й може да бъде представена с помощта на задача-игра. За целта модифицирахме една популярна през 80-години на миналия век игра, която на английски се нарича “Connect-Four” (“Свържи-четири”). Разликата е, че в оригиналния вариант се играе на дъска с 6 реда и 7 стълба, докато в предложената в Конкурса версия дъската е разширена до такава, с 10 реда и 10 стълба, а вместо 4 пула в ред, стълб или по диагонал, трябваше да бъдат наредени 5. Идеята на разширението беше, да не могат да се използват наготово съществуващи решения или поне да се наложи модификацията на съществуващи решения, ако участниците решат да използват такива.

Играта “Connect-Four” е сравнително прост представител на клас от игри, в които двама участници (обикновено наричани играч А и играч В, или първи  и втори играч, съответно) се редуват да правят ходове, спазвайки някакви правила, като всеки играч се стреми да достигне до конфигурация, определена от правилата на играта, която му носи победа. Ако никой от играчите не успее да достигне до печеливша конфигурация, играта завършва наравно. Типичен пример на такава игра е популярния по цял свят шахмат. Прелестта на тези игри е, че дори в ерата на компютрите, те продължават да привличат интереса на много любители и професионалисти, защото скоростта на работа на съвременните компютри  не позволява да се напише “програма-играч”, която на базата на пълното изчерпване на възможните конфигурации да гарантира победа.

Смело може да се каже,  че такова значимо направление на Компютърната наука като Изкуствения интелект е направило първите си стъпки, опитвайки се да моделира компютърно играта на най-добрите шахматисти. От позицията на натрупания опит може да се каже, че  да се моделира човешкото мислене (т.н. “базиран на знание” подход), дори в такава ограничена област като стратегическото единоборство на двама играчи, състезаващи се в условия на строго фиксирани правила, е по-скоро трудно. Причината за това изглежда е в дълбокото различие между принципите, върху които лежи човешкото мислене и организацията на съвременния фон Нойманов компютър (или неговата теоретична основа – машините на Тюринг). Значителните успехи на компютърните програми, играещи шахмат, в последните години се дължат не толкова на подобреното разбиране на това, как играят големите гросмайстори, а на непрекъснато увеличаващото се бързодействие на компютрите и възможността им да обработват за все по-кратко време все по-големи обеми от данни, но по свой си, машинен, начин (да наречем този подход “изчерпващ”).

Не, че базираният на знания подход – опитът да се моделира и програмира човешкото мислене – може да бъде тотално отречен. Просто нашето знание за работата на собствения ни мозък е все още недостатъчно (принципен въпрос е,  възможно ли е човешкият мозък да се самоанализира и да достигне достататъчно задълбочено разбиране за начина, по който самият той работи). Играта  “Connect-Four” е изиграла важна роля в изследването на горе поставените въпроси. Без да може да бъде атакувана с пълно изчерпване, тя е много по-проста от шахмата и позволява да бъде дълбоко анализирана. На любознателния читател бихме препоръчали дисертационния труд “A Knowledge-based Approach of Connect-Four” на холандския математик Victor Aliss. В него се доказва, че  на всяка дъска със 7 стълба и 2n реда, първият играч има печеливша стратегия, ако постави първия си пул в средната колона. При всяка друга игра на първия играч, като и при игра на дъска с 2m стълба и 2n реда, вторият играч може да завърши поне наравно. Дисертационният труд, програми играещи “Connect-Four”, както и други интересни материали свързани с играта може да намерите на адрес http://www.pomakis.com/~pomakis/c4.

Да разгледаме като пример някои (базирани на знание) правила, почерпени от работата на Victor Aliss. Нека са изиграни определен брой ходове на играта. В получената ситуация на дъската ще наричаме “X-заплаха” (X-threat) такава клетка, че ако играчът X я заеме – построява печеливша конфигурация. Очевидно не е смислено да се разглежда сериозно повече от една заплаха в стълб, защото заемането на най-ниско стоящата в стълба заплаха от съответния играч завършва играта. Ако играчът Y е на ход и може да заеме клетка, която е X-заплаха, трябва да го направи незабавно, защото ще загуби при следващия ход на Х. Ако Y е изправен пред повече от една Х-заплаха, то той вече е загубил играта. Очевидно е, че играчът, който е на ход, трябва добре да прецени съществуващите заплахи на противника и да не допуска ход, с който да позволи те да се осъществят. Ако пък не вижда опасност от заплахи на противника, тогава трябва така да избере хода си, че да се опита да създаде (по възможност повече) свои заплахи. Важна част на една печеливша стратегия е анализирането на противниковите заплахи и елиминирането на несъществените. За елиминирането на някои заплахи може да се използва фактът, че играчът А винаги прави нечетните, а играчът В – четните ходове.

От голямо значение за стратегиите базирани на знание е ситуацията в която всички ходове на играчът, който е на ход, са губещи. Тази ситуация се нарича “цугцванг”. Казваме, че играчът Х контролира цугцванга, ако може да играе така, че противникът му да попадне в цугцванг. Играчът, който успее да завземе контрола върху цугцванга си гарантира победата. При сравнително равностойна игра, победата обикновено се решава в последните ходове от цугцванг на един от състезателите.

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

Интересното е, че никой от участниците изглежда не е достигнал до идеята да използва стратегия, подобна на предложената в работата н Victor Aliss, и да играе за равен резултат като втори играч, тъй като броят на равните резултати в турнирната таблица е много малък. Възможно е  също така, участниците съзнателно да са заложили на по-агресивни стратегии, търсейки победата на всяка цена. Компромисът, както винаги изглежда най-доброто решение в такива ситуации – да си гарантираме първо равния резултат, а ако противникът ни даде шанс – да атакуваме.

Вторият подход – изчерпващият – е по-малко зависим от спецификата на конкретната игра. Ще се спрем тук на една от най-популярните стратегии за игри, в които двама играчи се редуват да правят ходове – т.н. alpha-beta-search. Използвали сме материали от съответната лекция в курса Алгоритми и структури от данни на Факултета по Информатика на Университета МакГилл.

Нека на всяка ситуация на игралната дъска да съпоставим връх на краен ориентиран граф и свържем два върха a и b на графа с ориентираното ребро (a,b) тогава и само тогава, когато в ситуацията a има допустим ход, който я довежда в ситуацията b. Ако една ситуация може да се получи по няколко начина, с различаващи се последователности от ходове, можем да използваме различни върхове за всеки един от начините. Така получаваме ориентирано кореново дърво, което наричаме дърво на играта. Коренът на дървото съответства на началото на играта, а листата – на заключителните ситуации и е естествено да бъдат надписани със съответния резултат  (за нашата задача това може да бъдат, например, 1 за победа на А, 0 – за равен резултат и –1 – за победа на В).

Да допуснем, че цялото дърво на играта може да бъде построено (вж. Фигурата). Тъй като всеки от двамата играчи се стреми да постигне максимално добър за себе си резултат и играчът А има първия ход, очевидно играта се подчинява на следната min-max идея. Играчът А избира всеки свой ход така че да max-имизира печалбата си, а играчът В така, че да min-имизира загубата. Започвайки от листата към корена на дървото, да съпоставим на всеки връх v, съответстващ на ход на играча В минимума на всички надписи на върхове, които са преки наследници на v. Аналогично да съпоставим на всеки връх w, съответстващ на ход на играча А максимума на всички надписи на върхове, които са преки наследници на w. Стойността приписана по този начин на корена е максималната печалба, която играчът А може да постигне при най-добра игра на В. Затова печелившата стратегия на А е да се придържа към един от тези пътища, от корена до някой лист, по които е получена максималната печалба. Всяко отклонение от този път на играча В само ще увеличи печалбата на А.

Фигура

Както вече споменахме построяването на пълното дърво, дори за такава опростена игра като “Connect-Four” е трудно осъществимо. За практически нужди трябва да се строят части от дървото. За нашата игра, в която трябва да се подредят 5 пула в редица е уместно да се строи дърво с корен текущия връх и височина 10, съответна на по 5 хода на всеки от партньорите. Ако по някой от клоновете един от играчите достигне печеливша позиция, този клон не е нужно да се проследява по надолу и на съответния връх се присвоява точна стойност на печалбата. Ако по някой от клоновете се достигне предварително избраната височина, без никой от играчите да достигне печеливша ситуация, тогава стойността на съответния връх трябва да се определи с помощта на съответна евристична оценъчна функция. Най-просто е такава ситуация да се определи като равна, но по-добре е да се използват някои от правилата базирани на знания, както бяха посочени по горе. Например,  за определяне на стойността да се използва броя на заплахите на всеки от двамата играчи.

Споменатият по-горе alpha-beta-search е вариант на описаната min-max-стратегия, който позволява, при добро стечение на обстоятелствата, цели клонове на дървото да бъдат отхвърляни без да се преглеждат изобщо. Същността на този вариант може да се демонстрира на примера от фигурата.  Да допуснем, че при  изследване на дървото сме установили стойност 7 за първия най-левия наследник на корена и започваме изследването на следващия наследник. Стойността му съгласно min-max стратегията ще бъде минимумът от стойностите на неговите наследници. Още първата стойност обаче е 6, тя е по-голяма или равна на минимума и значи този минимум ще бъде по-малък от намерената вече стойност 7 и не може да бъде стойност на корена, тъй като тя трябва да е максимум на стойностите на всичките му наследници. Затова всички останали клонове са безперспективни и няма нужда да се разглеждат. Аналогична е ситуацията и в третия връх от същото ниво. Първата стойност на която попадаме е 3 – по-малка от намерената вече 7 и затова поддърветата с корени в другите наследници на този връх няма нужда да се разглеждат. В най-лошия случай времето за работа на alpha-beta търсенето ще се изравни с това на основния алгоритъм, но в много случай ползата от него е несъмнена.

Няколко участника са използвали готови сорсове за Connect-Four, като са ги модифицирали да спазват променените правила на играта. Така е направил и победителят в кръга, Николай Милчев, който е използвал готово решение от Keith Pomakis (доколкото може да се съди по кода). Готовото решение за Connect-Four може да намерите на адреса споменат по-горе.

Ето как се представиха участниците според резултатите от проведения турнир на получените програми. Всяка програма трябваше да премери сили по два пъти с всяка друга програма – веднъж като първи и веднъж като втори играч. При равен резултат по-предно класиране се присъжда на този от състезателите, който има по добър резултат в преките двубои.

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

Supported by Musala Soft Ltd.

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