Þessi síða notar kökur (e. cookies) til að auðvelda þér að vafra um vefinn.

Alhliða Leikjaspilun og CadiaPlayer

UntitledÞað er liðin meira en hálf öld frá því að gervigreind varð að fræðasviði og alla vegi síðan þá hafa leikir spilað stórt hlutverk í framþróun hennar. Það mætti segja að fyrir mörgum rannsakendum gervigreindar séu leikir þeirra tilraunastofur því þeir eru upplagðir til að hafa stjórn á umhverfi rannsókna. Skák varð eins konar byrjunarreitur á leiðinni að því að leiða í ljós öll þau vísindi og kenningar sem þyrfti til að fá vélar til að sýna greind í hegðun sinni. Það kom reyndar á daginn að skák var mun meiri hindrun en gert var ráð fyrir og það liðu næstum 50 ár áður en tölvan Deep Blue frá IBM sigraði Garry Kasparov, þáverandi besta mennska skákmanninn. Nú á dögum hefur leikurinn Go tekið við af skák sem næsta áskorun á leiðinni að greindum kerfum, en sá leikur hefur mun stærra stöðurými en skák. Að auki hafði sú þekking sem fékkst með því að spila skákina ekki skilað sér í góðum Go spilurum.

 

Þegar skákáfanganum hafði verið náð þá stöldruðu samt margir við og bentu réttilega á að þrátt fyrir að það hefði vissulega mikið afrek unnist þá væri umdeilanlegt hversu mikil greind var í raun og veru á bak við Deep Blue. Tölvan var hlaðin af þekkingu um skák sem var forrituð beint inn í hana og var meira að segja vélbúnaður hennar sérstaklega hannaður til að tefla skák. Í stuttu máli þá gat Deep Blue bara teflt skák. Það var engin greind innan vélarinnar sem gat lært út fyrir mörk þessa eina leiks, ekki einu sinni mun einfaldari leiki. Gagnrýni á það hvort gervigreind væri á réttri leið kom jafnvel frá mönnum á borð við John McCarthy.

Alhliða Leikjaspilun

Árið 2005 setti Stanford Logic Group, undir forystu Michael Genesereth, á laggirnar nýtt undirsvið Gervigreindar sem þeir nefna Alhliða Leikjaspilun (e. General Game Playing). Þetta nýja svið hefur það að takmarki að þróa forrit sem þurfa ekki að treysta á forritara sína hvað varðar þekkingu til að geta spilað hvaða leik sem er vel. Þessi forrit fá aðeins að vita reglur leiksins sem þau eiga að spila með litlum fyrirvara og án þess að mannshöndin komi nálægt þurfa þau að móta eigin skoðun á hvernig best er að spila leikinn. Það er engin trygging fyrir því að forritið hafi séð eða spilað viðkomandi leik áður enda eru leikreglurnar búnar til í sérstöku máli sem getur spannað ógrynnin öll af leikjum. Leikirnir geta verið allt frá því að leysa þrautir yfir í að innihalda marga þátttakendur auk þess sem þeir geta einnig krafist samvinnu og samhliða aðgerða. Sem dæmi um leiki sem keppt hefur verið í má nefna, Checkers, Othello, Pentago, Amazons, 6 manna Chinese Checkers, Rubic’s Cube, Sudoku og Pac-Man. Að auki er vinsælt í keppnum að láta forritin keppa í leikjum sem hafa sérstaklega verið búnir til fyrir þær og því engin leið fyrir forritin að hafa séð þá fyrir.

Allt frá upphafi alhliða Leikjaspilunar þá hefur Stanford staðið fyrir árlegri keppni milli slíkra forrita á AAAI (Association for the Advancement of Artificial Intelligence) ráðstefnunni, en hún er ein af stærstu ráðstefnunum innan gervigreindar. Slíkar keppnir eru afbragðs leið til að þrýsta á framþróun sviðsins auk þess sem þær eru skemmtilegur vettvangur fyrir rannsakendur til að bera saman bækur sínar. Leikur milli alhliða leikjaspilara fer þannig fram að þau eru gangsett á vélum sem hafa aðgang að veraldarvefnum og bíða eftir að fá skilaboð frá sérstöku forriti er kallast Leikstjórnandi (e. Game Master). Leikstjórnandinn sér um að miðla leikreglum til keppendanna auk þess að segja þeim hvaða hlutverk þeir hafa í viðkomandi leik, t.d. hver er X og hver er O í myllu. Eftir að forritin hafa fengið leikreglurnar og smá tíma til að melta þær með sér hefst leikurinn og sér nú Leikstjórnandinn um að halda utan um framgang leiksins og miðla til forritana hvaða aðgerðir andstæðingur eða andstæðingar þeirra framkvæma, ef einhverjir eru. Þegar leikur nær endastöðu þá er hann gerður upp og geta forritin fengið á bilinu 0 til 100 stig.

Mynd2

CadiaPlayer

CadiaPlayer er Alhliða Leikspilunar forrit sem þróað var af greinarhöfundi og Dr. Yngva Björnssyni dósent við Háskólann í Reykjavík, en forritið dregur nafn sitt af gervigreindarsetri Háskólans í Reykjavík, CADIA (Center for Analysis and Design of Intelligent Agents). CadiaPlayer leit dagsins ljós árið 2007 og tók þátt í sinni fyrstu Alhliða Leikspilunar keppni það sama ár í Vancouver, Kanada. Þetta var í þriðja skiptið sem keppnin var haldin og höfðu þau forrit sem báru sigur úr býtum fyrstu tvö árin verið byggð á leitaraðferðum sem reynst höfðu vel í skák. En á þeim tíma voru nýir straumar byrjaðir að fanga athygli rannsakenda Go. Þessi leitartækni var kölluð Monte-Carlo Trjáleit (e. Monte-Carlo Tree Search) og jók hún getu Go forrita umfram það sem áður hafði þekkst. Þess skal þó getið að Monte-Carlo Trjáleit tekur ekki hefðbundnu leitaraðferðunum fram í skák og það er áhugavert rannsóknarefni hvaða eigindi leikja stjórna því hvort þeir henti annarri aðferðinni betur en hinni. Við gerð CadiaPlayer tókum við þessa nýju aðferðafræði við leit í leikjum og yfirfærðum hana til notkunar í Alhliða Leikjaspilun. Það er skemmst frá því að segja að CadiaPlayer tryggði sér sinn fyrsta heimsmeistaratitil í sinni fyrstu keppni á sannfærandi hátt og ruddi brautina fyrir Monte-Carlo Trjáleit sem vinsælastu aðferðafræðinni á bak við alhliða leikjaspilara. Enda hefur sigurvegari keppninnar frá 2007 til dagsins í dag alltaf verið byggður á Monte-Carlo Trjáleit.

Árið eftir var keppnin haldin í Chicago, Illinois í Bandaríkjunum og til leiks mætti endurbættur CadiaPlayer því þrátt fyrir velgengni fyrra árs þá sýndi forritið einnig veikleika í ákveðnum leikjum sem nú höfðu verið rannsakaðir og aðferðafræðin aðlöguð. Ennþá sýndi CadiaPlayer forritið að það var í fremstu víglínu varðandi notkun Monte-Carlo Trjáleitar í Alhliða Leikjaspilun því það gerði sér lítið fyrir og sigraði keppnina aftur og varð með því fyrsta forritið til að sigra hana tvisvar. Árið 2009 var keppnin haldin í Pasadena, California í Bandaríkjunum, en það árið varð CadiaPlayer að sætta sig við sjötta sætið á meðan nýr heimsmeistari var krýndur, forrit er nefndist Ary þróað af Háskólanum í París. Ary hélt áfram sigurgöngu sinni árið 2010 í Atlanta, Georgia í Bandaríkjunum en CadiaPlayer náði þriðja sætinu. CadiaPlayer komst svo í annað sætið í keppninni 2011 sem haldin var í Barcelona á Spáni en þar bættist nýtt forrit, TurboTurtle, í hóp þeirra er sigrað hafa þessa keppni. TurboTurtle var skrifað af fyrrverandi nemanda í Stanford sem nú starfaði hjá Google. Í ár endurheimti CadiaPlayer heimsmeistaratilinn í Alhliða Leikjaspilun og varð með því fyrsta forritið til að vinna keppnina þrisvar sinnum.

Lokaorð

Árið 2012 útskrifaðist ég með doktorsgráðu í tölvunarfræðum frá Háskólanum í Reykjavík. CadiaPlayer byrjaði sem rannsóknarverkefni mitt í meistaranámi mínu við sama skóla og varð seinna aðal verkfæri rannsókna doktorsritgerðar minnar sem var unnin undir leiðsögn Dr. Yngva Björnssonar. Rannsóknir á Alhliða Leikjaspilun falla vel að markmiðum greindra kerfa, því slík kerfi eiga að geta starfað sjálfstætt, lært af sjálfsdáðum og brugðist við áður óséðum tilvikum. Með rannsóknum tengdum CadiaPlayer ásamt frábærum stuðningi frá Háskólanum í Reykjavík hef ég getað ferðast til hinna ýmissa staða hvort sem er til að tala á ráðstefnum, við skóla eða kynnast nýjum sjónarhornum. Það er óhætt að segja að CadiaPlayer hefur reynst mér góður félagi sem hefur bæði leyft mér að upplifa einstaka hluti og kynnt mig fyrir fjölmörgu áhugaverðu fólki. Það var því sérstaklega ánægjulegt að lokapunkturinn á námi mínu var að leiða CadiaPlayer til sigurs í ár og gera hann að núverandi heimsmeistara í Alhliða Leikjaspilun.

Höfundur: Hilmar Finnsson, nýdoktor í tölvunarfræði við Háskólann í Reykjavík

Lesið 4885 sinnum Síðast breytt fimmudagur, 16 Maí 2013 16:03