consourceforge.jp

TowardsQuantifyingInteractionNetworksinaFootballMatchOliverM.
Cliff,JosephT.
Lizier,RosalindX.
Wang,PeterWang,OliverObst,andMikhailProkopenkoCSIROInformationandCommunicationTechnologiesCentre,AdaptiveSystems,P.
O.
Box76,Epping,NSW1710,AustraliaAbstract.
Wepresentseveralnovelmethodsquantifyingdynamicinteractionsinsimulatedfootballgames.
Theseinteractionsarecapturedindirectednetworksthatrepresentsignicantcoupleddynamics,detectedinformation-theoretically.
Themodel-freeapproachmeasuresinformationdynamicsofbothpair-wiseplay-ers'interactionsaswellaslocaltacticalcontestsproducedduringRoboCup2DSimulationLeaguegames.
Thisanalysisinvolvescomputationofinformationtransferandstorage,relatingtheinformationtransfertoresponsivenessoftheplayersandtheteam,andtheinformationstoragewithintheteamtotheteam'srigidityandlackoftacticalexibility.
Theresultantdirectednetworks(interac-tiondiagrams)andthemeasuresofresponsivenessandrigidityrevealimplicitinteractions,acrossteams,thatmaybedelayedand/orlong-ranged.
Theanaly-siswasveriedwithanumberofexperiments,identifyingthezonesofthemostintensecompetitionandtheextentofinteractions.
1IntroductionManyteamgames,realandvirtual,arecharacterisedbyrichinteractionsoccurringdynamicallyandshapingthecourseofthecontestbothlocallyandglobally.
Theinter-actionsacrosstheteamsarecreatedbyopposingobjectivesofcompetingplayersandtacticalschemes.
Theinteractionswithinateamareusuallyconstrainedbycooperationandsharedplans.
Generally,theinteractionsaredirected(e.
g.
,adefenderismarkinganopponent'sforward),varyinginstrengthovertimeand/orspace,andtypicallydonotresultfromdirectmessagingorcommunications—rathertheymanifestsometacitcorrelationsthatoftenaredelayedintimeand/orarelong-rangedovertheplay-eld.
Whileasignicantnumberofpatternsemergingduringagamemaybeevidentevenwithoutanin-depthanalysis,mostoftheinteractionsmayappearintractabletoanex-ternalobserverwhodoesnothaveanaccesstothelogicandneuralprocessingoftheplayers.
Onethenmayformulateageneralproblem:howcananexternalobserveriden-tifymostgenericinteractionnetworksthatlinktogetherautonomousplayers,withoutre-constructingtheplayers'behaviourandusingonlythepositionaldata,suchaspla-narcoordinatesandtheirchangesTheproblemisdifcultassomeofthedependenciesbetweenplayersarenotdiscerniblesimplybycorrelatingtheirdynamiclocationsovertime—oneneedstotakeintotheaccountapossiblydirectednatureofsuchcorrela-tions,wheredynamicsofoneoftheplayersaffectsthepositioningofanother.
Ingeneral,asmentionedbyVilaretal.
[1],"quantitativeanalysisisincreasinglybeingusedinteamsportstobetterunderstandperformanceinthesestylized,delineated,S.
Behnkeetal.
(Eds.
):RoboCup2013,LNAI8371,pp.
1–12,2014.
cSpringer-VerlagBerlinHeidelberg20142O.
M.
Cliffetal.
complexsocialsystems".
Oneoftheolderexamplesis"sabermetrics"—thespecialisedanalysisofbaseballthroughobjectiveevidence,e.
g.
baseballstatisticsmeasuringin-gameactivity[2].
AnotherrecentexampleisdescribedbyFewelletal.
[3]whoanalysedbasketballgamesasnetworks,whereplayersarerepresentedasnodesandpassesasedges:theresultingnetworkcapturesballmovement,atdifferentstagesofthegame.
Theirworkstudiesnetworkproperties(degreecentrality,clustering,entropyandowcentrality)acrossteamsandpositions,andattemptstodeterminewhetherdifferencesinteamoffensivestrategycanbeassessedbytheirnetworkproperties.
StrategicnetworksanalysedbyFewelletal.
consideronlyexplicitinteractions(suchaspasses)withinateam,andnotimplicit(delayedand/orlong-ranged)interactions,acrossteams.
AnotherveryrecentinvestigationbyVilaretal.
[1]proposedanovelmethodofanal-ysisthatcaptureshowteamsoccupysub-areasoftheeldastheballchangeslocation.
Thisstudywasimportantinfocussingonthelocaldynamicsofteamcollectivebehav-iorratherthanindividualplayercapabilities:whenappliedtofootball(soccer)matches,themethodsuggestedthatplayers'numericaldominanceinsomelocalsub-areasisakeyto"defensivestability"and"offensiveopportunity".
Whilethemethodrigorouslyusedaninformation-theoreticapproach(e.
g.
theuncertaintyoftheteamnumericalad-vantageacrosssub-areaswasdeterminedusingShannon'sentropy),itwasnotaimedatanddidnotproduceinteractionnetworks,eitherexplicitorimplicit.
Constructionofinteractionnetworksfor(possiblycompeting)teamsisnotuniquetosport,butarguablyitsutilitycanbeleveragedquitestronglyinteamgames,suchasfootball,basketballandsoon.
RoboCup2DSoccerSimulationLeagueisawell-knownbenchmarkdomainforArticialIntelligencethatspecicallytargetssoccerwithitsrealisticandchallengingmulti-agentdynamics,characterisedbyautonomousdecision-makingunderconstraints,setbytacticalplansandteamwork(collaboration)aswellasopponent(competition)[4,5,6,7,8,9,10,11],andsoweusethisdomaininourstudy.
Informationdynamicsisarecentmethodologyforanalysisofcomplexsystemsingeneralandswarmbehaviorinparticular.
InthispaperwedescribeanovelapplicationofinformationdynamicstotheRoboCup2DSimulation.
Inparticular,wedevelopanapproachtobuildseveralinteractiondiagrams,givendatafromanumberofgames,followedbyatacticalanalysis.
Theinteractiondiagramsrevealafewinterestingde-pendenciesbetweenpairsofplayersthatareusefulforgameanalysis,whilethetacticalanalysisextendsthesendingstoformation-levelinteractions(e.
g.
,betweendefensiveline-upofteamYwiththeattackingline-upofteamX,etc.
).
2MotivationandApproach2.
1InformationDynamicsArecentlydevelopedframeworkofinformationdynamicsstudiesthephenomenonofcomputationinasystematicway:ituncoversandanalysesinformation-theoreticrootsofthemostbasiccomputationalprimitives:storage,transmission,andmodicationofinformation[12,13,14,15].
Theactiveinformationstoragequantiestheinformationstoragecomponentthatisdirectlyinuseinthecomputationofthenextstateofaprocess[15].
Morepre-cisely,itistheaveragemutualinformationbetweenthesemi-innitepastoftheprocessTowardsQuantifyingInteractionNetworksinaFootballMatch3x(k)n={xnk+1,xn1,xn}(ask→∞)anditsnextstate.
Thelocalinformationstorage(orpointwisemutualinformation)isthenameasureoftheamountofinforma-tionstorageinusebytheprocessataparticulartime-stepn+1:aX(n+1)=limk→∞log2p(x(k)n,xn+1)p(x(k)n)p(xn+1).
(1)Inpractice,onedealswithnite-kestimatesaX(n+1,k),aswellasthenite-kesti-matesAX(k)oftheaverageactiveinformationstorageAX=aX(n+1)n.
Transferentropy[16]isdesignedtodetectasymmetryintheinteractionofsubsys-temsbydistinguishingbetween"driving"and"responding"elements.
Thelocalinfor-mationtransfer,basedontransferentropy,capturesinformationtransmission[12]fromsourceYtodestinationX,ataparticulartime-stepn+1.
Itisdenedastheinformationprovidedbythesourceynaboutthedestination'snextstatexn+1thatwasnotcontainedinthepastofthedestinationx(k)n:tY→X(n+1)=limk→∞log2p(xn+1|x(k)n,yn)p(xn+1|x(k)n).
(2)Itisimportanttorealisethatinformationtransferbetweentwovariablesdoesnotre-quireanexplicitcommunicationchannel,itratherindicatesahighdegreeofdirectionalsynchronyornonlinearcorrelationbetweenthesourceandthedestination.
Itcharac-terisesadegreeofpredictiveinformationtransfer,i.
e.
,"ifthestateofthesourceisknown,howmuchdoesthathelptopredictthestateofthedestination"[12].
Sometimesitisusefultoconditionthelocalinformationtransferonanothercon-tributingprocessW,consideringthelocalconditionaltransferentropy[13]:tY→X|W(n+1)=limk→∞log2p(xn+1|x(k)n,yn,wn)p(xn+1|x(k)n,wn).
(3)InthisstudyweusedtheaverageinformationtransfertY→X|W=tY→X|W(n+1)n.
Onemay,however,utiliselocalvaluesaswellinordertotracetheinformationdynamicsovertime,e.
g.
identifyingitspeaksduringspecicmoments.
2.
2Pair-WiseInformationDynamicsandInteractionDiagramsInordertoestimatestrengthofdirectedcouplingbetweentwoagentswecomputetheaveragetransferentropybetweenthemduringanygivengame.
ForagamegwithNtimesteps,betweentwoteamsXandY,thelocaltransferentropyateachtimestepn≤NiscalculatedbetweeneachsourcevariableYi(achangeinthe2DpositionalvectorofagentifromteamY)anddestinationvariableXj(achangeinthe2DpositionalvectorofagentjfromteamX),giventhechangeincurrent2Dballpositionb:tgYi→Xj|b(n).
Dynamicsoftheballisconditioneduponinordertocomputethetransferentropyincontextofthegame,whichisgreatlyaffectedbytheballtrajectories.
Then,theaveragetransferentropyforeachsource-destinationpairovertheentirematchiscalculatedas4O.
M.
Cliffetal.
TgYi→Xj|b=1NN1n=0tgYi→Xj|b(n).
(4)Information-SinkDiagrams.
Oncethegame'saveragetransferentropy,TgYi→Xj|b,isdeterminedforeachpairYi,Xj,weidentifythesourceagentYi(Xj,g)fromtheopposingteamthattransfersmaximalinformationtoagivenagentXj:Yi(Xj,g)=argmaxYk∈YTgYk→Xj|b.
(5)OveranumberofgamesG,weselectthesourceagentYi(Xj)thattransfersmaxi-malinformationtoXjmostfrequently,asthemodeoftheseries{Yi1(Xj,1)YiG(Xj,G)}.
Then,weconsidertheaverageinformationtransferbetweenthesetwoagentsYi=Yi(Xj)andXjacrossallgames:TYi→Xj|b=1GGg=1TgYi→Xj|b.
(6)Intuitively,themovementofthesourceagentYi=Yi(Xj)affectedtheagentXjmorethanmovementofanyotheragentinteamY.
Thatis,theagentXjwasrespon-sivemosttomovementofthesourceagentYi.
Crucially,whenweusethenotionofresponsivenesstoanother(source)agent,wedonotloaditwithsuchsemanticsasbe-ingdominatedby,ordrivenbythatotheragent.
Higherresponsivenessmayinfactreecteitherusefulreactiontotheopponent'smovements(e.
g.
,goodmarkingofthesource),orahelplessbehaviour(e.
g.
,constantchaseafterthesource).
Viceversa,gen-eratingahighresponsivenessfromanotheragentmayresultineitherausefuldynamic(e.
g.
,positionaloreventacticaldominanceovertherespondingagent),orawastefulmotion(e.
g.
,beingsuccessfullymarkedbytherespondingagent).
Inshort,responsive-nesscapturedinthemaximaltransferTYi→Xj|bdetectsadirectedcouplingfromthesourceagentYitotherespondingagentXjandshouldnotbeinterpretedingeneralasasimpleindexforcomparativeperformance.
Itis,however,ausefulidentieroftheopponents'sourceplayerthatwasaffectingagivenagentXjmost.
Givenaseriesofgames,weidentifythepairs"source-responder"byndingthesourceagentforeachoftheagentsonbothteams(alwayschoosingthesourceamongtheopponents).
Theidentiedpairscanbevisualisedinan"information-sink"interac-tiondiagramD(Y,X)thatdepictsadirectedgraphwith20nodesrepresentingplay-ers(typicallyexcludinggoalkeepers),withtheedgesrepresentingallsource-responderpairs,whereasingleedgeisincomingtoeveryagentfromthecorrespondingsource.
Figure1ashowstheinformation-sinkinteractiondiagramD(Oxsy,Gliders)builtforseveralhundredgamesbetweenOxsyandGliders(cf.
Resultssection).
Information-BaseDiagrams.
Similarly,havingobtainedtheaveragetransferentropyduringagame,TgYi→Xj|bforallpairs,weidentifytheresponderagentˇXj(Yi,g)that"received"maximalinformationfromagivenagentYi.
Formally,foranygameg:ˇXj(Yi,g)=argmaxXk∈XTgYi→Xk|b.
(7)TowardsQuantifyingInteractionNetworksinaFootballMatch5OveranumberofgamesG,weselecttheresponderagentˇXj(Yi,g)towhommax-imalinformationwastransferredbyYimostfrequently,asthemodeoftheseries{ˇXj1(Yi,1)XjG(Yi,G)}.
Finally,weconsidertheaverageinformationtransferbetweenthesetwoagentsYiandˇXj=ˇXj(Yi,g)acrossallgames:TYi→ˇXj|b=1GGg=1TgYi→ˇXj|b.
(8)Thepairs(Yi,ˇXj)identiedforeachagenttreatedasasourcearecombinedinan"information-basediagram"ˇD(Y,X).
Theintuitioninthiscaseisthesameasintheprevioussubsection—thedifferenceisthatnowweidentifythehighestresponderagent,havingselectedasource.
Ingeneral,ofcourse,thepair(Yi,Xj)denedfortheinformation-sinkdiagramsandthepair(Yi,ˇXj)denedfortheinformation-basediagramsmaydiffer.
Thatis,theagentYimaybethemostinformativesourceYifortheagentXj,amongallpossiblesourcesinY,buttheagentXjmaybenotthebestresponderˇXtotheagentYiamongallpossiblerespondersinX,andviceversa.
Whileaninformation-sinkdiagramreectsmorewheretheinformationtendstobetransferredto,aninformation-basediagramtendstodepictwheretheinformationistransferredfrom.
Neitherofthediagramspresentsacomplete"story",highlightingonlyasmallpartoftheoverallinformationdynamics.
Therearemorecomprehensivedia-grams,wheretheedgeswouldrepresentinthedescendingorderthehighestinformationtransfersforallthepairs,retainingagivennumberofsuchlinks,orkeepingtheedgesfortheinformationamountsaboveacertainthreshold,etc.
—intheseinstances,someagentsmayhavenoincomingoroutgoinglinksatall.
Nevertheless,webelievethattheinteractiondiagramspresentedherearevaluable,beingparticularlysimpleandeasytointerpret.
Specically,foraninformation-sinkdiagrameveryagenthasanincomingedge,andforaninformation-basediagrameveryagenthasanoutgoingedge.
Figure2ashowstheinformation-baseinteractiondiagramˇD(Oxsy,Gliders)builtforseveralhundredgamesbetweenOxsyandGliders(cf.
Resultssection).
2.
3TacticalAnalysisBuildingupontheinformationdynamicsmeasures,itispossibletoinvestigategroupbehaviorincomplexsystems,suchasswarms.
Forinstance,recentstudiesbyWangetal.
[17]quantitativelyveriedthehypothesisthatthecollectivememorywithinaswarmcanbecapturedbyactiveinformationstorage.
Highervaluesofstorageareassociatedwithhigherlevelsofdynamiccoordination,whileinformationcascadesthatcorrespondtolongrangecommunicationsarecapturedbyconditionaltransferentropy[12,13].
Inotherwords,informationtransferwasshowntocharacterisethecommunicationaspectofcollectivecomputationdistributedwithintheswarm.
InapplyinginformationdynamicstotheRoboCup2DSimulationLeaguewemakethefollowingconjecture:ahigherinformationtransfertY→X|WfromthesourceY(e.
g.
dynamicsofplayerY)tothedestinationX(e.
g.
,dynamicsofanotherplayerX),inthecon-textofsomeotherdynamicsW(e.
g.
,themovementoftheballW),isindicativeofahigherresponsivenessoftheprocess/playerXtotheprocess/playerY.
6O.
M.
Cliffetal.
Thatis,the"destination"playerYresponds,forexample,byrepositioning,tothemove-mentofthe"source"playerY.
Thismayapplytomanysituationsontheeld,forin-stance,whenoneteam'sforwardsaretryingtobetteravoidopponent'sdefenders,weconsidertheinformationtransfertYdef→XattfromdefendersYi∈YdeftoforwardsXj∈Xatt,wheretheinvolvedprobabilitydistributionsareobtainedfordifferentrela-tivepositionsonthesoccereld.
Viceversa,thedynamicsoftheopponent'sdefenders,whoaretryingtobettermarkourteam'sforwards,arerepresentedintheinformationtransfertXatt→YdeffromforwardsXj∈XatttodefendersYi∈Ydef.
Thesetwoex-amplesspecicallyconsideracouplingbetweentheattacklineXattofourteamandthedefenselineYdefofopponent'steam(henceforthwekeepdenotingopponent'slines(attack,mideldordefense)byYlineandourteam'slinesbyXline).
Wefurthercontrastthesetwotransfersinthecoupledlines:Δ(Xatt,Ydef)=tYdef→XatttXatt→Ydef.
(9)Whenourforwardsaremoreresponsiveonaveragetotheopponent'sdefendersthantheopponentsdefendersaretoourforwards,tYdef→Xatt>tXatt→Ydef,andtherelativeresponsivenessΔ(Xatt,Ydef)>0.
Itisalsopossibletocombinerelativeresponsive-nessscoresforeachofthecoupledlinesintheoveralltacticalrelativeresponsiveness(including,forexample,relativescoresformideldersXmidandYmid):Δ(X,Y)=Δ(Xatt,Ydef)+Δ(Xdef,Yatt)+Δ(Xmid,Ymid).
(10)HereallthetransferstoteamXareaddedup,andthetransfersfromteamXaresub-tractedaway.
WheneachofthetransfersisconditionedonsomeothercontributorW(e.
g.
,allthedynamicsarecomputedinthecontextoftheballmovement),theoveralltacticalrelativeresponsivenessΔ(X,Y|W)isalsoplacedinthisspeciccontext,W.
Inprinciple,competitivesituationsresultinquitevigorousdynamicswithinthein-volvedlinesandoverallformations,andtheteamthatmanagestoachieveahigherdegreeoftacticalrelativeresponsivenessdoesoftenperformbetter.
Whilethisisnotahardrule,wemaycorrelatethescoresofrelativeresponsiveness(e.
g.
,line-by-line)withthegamescores,andidentifythelineswhichimpactedonthegamesmore.
Ourtacticalanalysisalsoinvolvescomputationoftheactiveinformationstoragewithintheteams.
Wecharacteriseteam'srigidityAXastheaverageofinformationstor-agevaluesforallplayersoftheteam.
WealsodeterminetherelativerigidityA(X,Y)=AXAYfortheteams(ortheircoupledlines).
ThehypothesishereisthatahigherrigidityAXwithintheteamisindicativeofahigherdependenceofplayersoneachother,orahigherredundancywithintheteam'smotion.
Theaverageinformationstorage,orrigidityAX,ishighwheneveronecanpredictthemotionofsomeplayersbasedonthemovementsoftheirotherteammates.
Inthesecases,theplayersarenotasindependentofeachotherasatrulycomplexorswarmbehaviorwouldwarrant,makingthetacticslessversatile.
Obviously,thismaybecounter-productive,sinceanopponentteamcancounteractbyonlypartiallyob-servingthe'rigid'team'sdynamics,anddeducingtherest.
Consequently,therelativerigidityA(X,Y)shouldbeanti-correlatedwiththeteamXperformanceagainstteamY.
TowardsQuantifyingInteractionNetworksinaFootballMatch73ResultsTocomputethemeasuresdescribedinprevioussections,produceinteractiondiagramsandcorrelatetacticalresponsivenesswithteamperformance,wecarriedoutmultipleiterativeexperimentsmatchingGliders2013upagainstsomewell-knownteams,suchasOxsy[18]andMarlik[19].
Thecorrelationscores(Pearsonproduct-momentcorrelationcoefcients)reportedbelowweretestedforstatisticalsignicance,andcorrectedformultiplecomparisons.
3.
1InteractionDiagramsFigure1presentstheinformation-sinkinteractiondiagramD(Oxsy,Gliders)andtheinformation-baseinteractiondiagramˇD(Oxsy,Gliders),builtoveralmost500hundredgamesbetweenOxsyandGliders.
Analogously,Fig.
2showstheinformation-sinkinteractiondiagramD(Marlik,Gliders)andtheinformation-baseinteractiondiagramˇD(Marlik,Gliders),builtovernearly450hundredgamesbetweenMarlikandGliders.
(a)Information-sinkdiagramforGliders(left)andOxsy(right)(b)Information-sinkdiagramforGliders(left)andMarlik(right)Fig.
1.
Interaction-sinkdiagrams.
Arrowsrepresenthighestinformationtransferbetweenplayers.
MATLABcoppercolormapisusedtoindicatethestrengthoftransfer,varyingsmoothlyfromblack(weakest)tobrightcopper(strongest).
Exampleinteractions:twoarrowsintheleftdiagramfromOxsy'scentralmid-elder,positionedinthecentrecircle,toGliders'leftandrightdefendersindicatethatthesedefendersrespondmostlytothecentralmid-elder'smotion.
Severalinterestingobservationscanbemade.
Ingeneral,thediagramsarehighlysymmetricwithrespecttoleftandrightwings.
Thediagramsrepresentinteractionsav-eragedovermanygames,andsothesymmetrydemonstratesthattheemployedmethodsarerobusttonoisepresentinindividualgames.
Also,theinformation-sinkdiagramsdodifferfrominformation-basediagrams,asexpected.
Webeginamoredetailedanalysiswiththeinformation-sinkinteractiondiagrams1aand1b:–Gliders'defendersmostlyrespondtoopponent'scentralmid-elder;–Gliders'mid-eldersmostlyrespondtoopponent'scentralmid-elder;–Gliders'forwardsmostlyrespondtoOxsy'sdefendersorMarlik'scentralmid-elder;8O.
M.
Cliffetal.
(a)Information-basediagramforGliders(left)andOxsy(right)(b)Information-basediagramforGliders(left)andMarlik(right)Fig.
2.
Interaction-basediagrams.
Arrowsrepresenthighestinformationtransferbetweenplay-ers.
MATLABcoppercolormapisusedtoindicatethestrengthoftransfer,varyingsmoothlyfromblack(weakest)tobrightcopper(strongest).
Exampleinteractions:fourarrowsintherightdiagramfromMarlik'scentralmid-elder,positionedinthecentrecircle,toallGliders'defendersindicatethatthedefendersrespondmostlytothecentralmid-elder'smotion.
–Oxsy'swingforwardsmostlyrespondtoGliders'sidedefenders,whileOxsy'scentre-forwarddoesnotmostlyrespondtoGliders'centre-backs;–Oxsy'ssidedefendersmostlyrespondtoGliders'wingforwards,whileOxsy'scentre-backsdonotmostlyrespondtoGliders'centre-forward;–Marlik'sforwardsmostlyrespondtoGliders'centralmid-elder;–Marlik'sdefendersmostlyrespondtoGliders'side-wingers.
Nowweturnourattentiontotheinformation-baseinteractiondiagrams2aand2b:–Gliders'defendersmostlytransferinformationtoOxsy'swingforwards,butnottotheircentre-forward;–practicallyeveryOxsy'splayertransfersinfromationtoGliders'centre-forward;–Gliders'defendersmostlytransferinformationtoMarlik'scentre-forward,butnottotheirwing-forwards;–Gliders'centre-forwardistransferredinformationfrommanyMarlik'splayers,butnotfromtheirsidedefenders;–Gliders'swingforwardsaretightlycoupledwithMarlik'ssidedefenders.
EvensuchabriefanalysishelpstopointoutthatinthecontestwithOxsy,Glidershaveaproblemwiththeircentre-backsnotactivelycheckingtheopponent'scentre-forward,butasimilarproblemalsoexistsinOxsy'sowndefense.
Notsurprisingly,mostgoalsarescoredinthesegamesthroughthecentreandnotviathewingattacksandcrosses.
Inaddition,itappearsthatalotofGliders'motionistunedtoopponents'centralmid-elderwhichhighlightsahighdegreeofredundancythatmayneedtobeexploited.
InthegamesagainstMarlikitisevidentthattheopponentscentralmid-elderplaysakeyroleinbothdefenseandattack,whichagainpresentsanopportunitytoexploitsuchanoverload.
Atthesametime,itappearsthatalotofinteractionsoccurontheanksofMarlik'sdefense(defendersmarkforwardswhotrytoevade),whileMarlik'swingforwardsarenotmarkedbyGliders'ssidedefenders.
TowardsQuantifyingInteractionNetworksinaFootballMatch93.
2TacticalAnalysisInthissubsection,wecorrelatescoresofrelativeresponsiveness(eitherline-by-lineoroverall),aswellasrigidity,withthegamescores,andidentifythelineswhichimpactedonthegamesmore.
Thatis,wecomputeacorrelationcoefcientbetweenaseriesofgamescoresandaseriesofinformationvaluespergame.
TheanalysisofthegamesbetweenGlidersandOxsyshowsthatasufcientlyhighcorrelation(ρ1=0.
425)existsbetweenthegamescoreandonlyonerelativerespon-sivenessΔ(Glidersdef,Oxsyatt).
Thatis,thegamesbetweenthesetwoteamsaredecidedmostlyintheoppositionbetweenGliders'defendersandOxsy'sforwards.
SpecicallyonemayconjecturethatwhenevertheOxsy'sforwardsaremoreresponsiveinevadingthedefense,Oxsytendtowin,andwheneverGliders'defendersaremoreagileinclosingontotheforwards,Gliderstendtowin.
However,themaininformationtransfercomponentofΔ(Glidersdef,Oxsyatt),cor-relatedwiththeperformance,istOxsyatt→Glidersdef,at0.
553("ourresponsivenesshelpsourscoreline"),whilethecorrelationwithtGlidersdef→Oxsyattisjust0.
089("opponentsresponsivenessdoesnothurtourscoreline").
ThismeansthatonaveragetherelativeagilityofGliders'defendersiscorrelatedwiththescorelinemorethantheresponseofOxsy'sforwards.
Thisisnotacausalinference,butsimplyacorrelationobservation.
ThedynamiccontestsbetweenGliders'forwardsandOxsy'sdefenders,orbetweenthemideldplayers,donotseemtobegreatlycorrelatedwiththescorelineonav-erage(thescorelineiscorrelatedwithΔ(Glidersatt,Oxsydef)atjust0.
099,andwithΔ(Glidersmid,Oxsymid)atjust0.
216).
Thetransfercomponentsofthesecharacteris-ticsdonotshowanyhighercorrelationseither.
Theoveralltacticalrelativeresponsive-nessΔ(Gliders,Oxsy)iscorrelatedwiththescorelineatacrediblelevelof0.
310.
Asexpected,therelativerigidityA(Gliders,Oxsy)=AGlidersAOxsyisobservedtobehighlyanti-correlatedwiththescoreline:ρ=0.
641.
Themaincontributingpartisfoundtobetherigidityofthemid-elders:thecorrelationofrigidityA(Glidersmid,Oxsymid)withtheperformanceisalsoquitehighat0.
503,andthemajorcomponentofthiscomesduetotherigidityofOxsy'smid-elders:correlationofA(Oxsymid)is0.
377(itispositiveasthescorelineispresentedasGlidersvsOxsy,sothathighergamescoresforGlidersarecorrelatedwithhigherOxsy'srigidity).
ThetacticalanalysisofthegamesbetweenGlidersandMarlikproducesmostlycon-curringobservations.
Inthispair,theoutcomeismostlydecidedinthecontestbetweenGliders'attackandMarlik'sdefense:thecorrelationbetweenrelativeresponsivenessΔ(Glidersatt,Marlikdef)islowbutstatisticallysignicant:0.
157.
Interestingly,how-ever,bothindividualcomponentsareanti-correlatedwiththescoreline:thetransfertMarlikdef→Glidersattisanti-correlatedat0.
210,andthetransfertGlidersatt→Marlikdefisanti-correlatedat0.
366.
Thisposesaninterestingquestion:whytwoindividualcomponentsoftherelativeresponsivenessarebothanti-correlatedwiththescoreline,buttheircombinationispos-itivelycorrelated,albeitatalowlevelOnepossibleexplanationisasfollows.
Bothinvolvedgroups(GlidersforwardsandMarlikdefenders)areinalmostconstantinter-dependentmotionthatoftenconfoundstheplayers.
WhenMarlikdefendersrespondtoGlidersforwards'attemptstondfreespots,theyeffectivelymarkand/orblocktheforwards,resultinginlowerscoresforGlidersteam—hence,thenegativecorrelation10O.
M.
Cliffetal.
betweentGlidersatt→Marlikdefandthescoreline,whichisseenfromtheGliders'perspec-tive("opponentsresponsivenesshurtsourscoreline").
However,whenGlidersforwardsrespondtoMarlikdefenders'attemptstomarkthem,theymayabandongoodscoringpositions,alsoresultinginlowerscoresforGlidersteam—hence,thenegativecorre-lationbetweentMarlikdef→Glidersattandthescoreline("ourresponsivenessalsohurtsourscoreline").
Nevertheless,whenthescorelineiscorrelatedwiththerelativeresponsive-ness,ratherthantheindividualcomponentsofthelatter,theresultispositivebutlow.
Thismeansthattheremainingdifferenceisstillslightlyimportantbecauseoftheinter-dependenceofmotion:whenGlidersforwardsreposition,theyattractMarlikdefendersagain,andthe'circle'repeats,untilonesidegainsabriefadvantage("whenourrespon-sivenessishigherthanopponentsresponsiveness,ithelpsourscoreline").
Inshort,itisnotthelevelofourresponsivenessthatispositivelycorrelatedwiththescoreline,butthelevelofrelativeresponsiveness.
Therearenosurpriseswiththeanalysisofrigidity:therelativerigidityA(Gliders,Marlik)=AGlidersAMarlikishighlyanti-correlatedwiththescoreline:ρ=0.
505.
Itisinterestingthat(relative)rigiditiesofseparategroups(defense,mid-eld,attack)werenotfoundtobecorrelatedsignicantlywiththeoutcomes:thedependenceisdetectedonlyattheoverallteamlevel,beingarguablyanemergentpropertyinthiscontest.
Insummary,thendingsdemonstrateapplicabilityoftheinformationdynamicsmeasurestoanalysisoffootballmatches,revealingtheareasofmostintensecompe-titionandtheextentofinteractions.
ThelatteraspectisevidentwhenonecomparestheinterpretationsofrelativeresponsivenessinthegamesagainstOxsyandagainstMar-lik.
ThehigherresponsivenessofGliders'defenderstoOxsy'sforwardswasfoundtobepositivelycorrelatedwiththescoreline,whilethehigherresponsivenessofGlid-ers'forwardstoMarlik'sdefenderswasanti-correlated(aswastheresponsivenessofMarlik'sdefenderstoGliders'forwards).
Thedifferenceshowsthatintherstcaseresponseswereproductiveandtheinteractionwasclearlydirectional,whileinthesecondinstance,theresponseswerestronglyinterdependentandtheinteractionwasquitecircular.
Theseobservationsarealsosupportedbytheinteractiondiagrams:bothinformation-sinkandinformation-basediagrams1aand2aforGlidersvsOxsyshowthatGliders'defendersrespondstronglytoOxsy'sforwards,whiletheinformation-sinkandinformation-basediagrams1band2bforGlidersvsMarlikhighlighttheextentofcross-couplingbetweenGliders'forwardsandMarlik'sdefenders.
Theanti-correlationofrigidityinbothexperimentalset-upsisalsoencouraging:thismeasurecanbesug-gestedasasimplerobustmeasureoftacticalexibility,attheemergentteamlevel.
4ConclusionThepaperproposedanapproachforconstructinginteractionnetworksthatrevealsig-nicantcoupleddynamicsproducedduringteamgames,orotheractivitiesthatarecharacterisedbyconcurrentcooperationandcompetition.
Theapproachusesanovelapplicationofinformationdynamicsanalysingpair-wiseinteractionsandgroup-leveltacticsofRoboCup2DSimulationLeaguegames.
Theinputdataneededfortheanal-ysiscontainonlypositionaldata,suchasplanarcoordinatesandtheirchanges,fol-lowedbycomputationofcorrespondingprobabilitydistributionsandlocalinformationTowardsQuantifyingInteractionNetworksinaFootballMatch11transfermeasures.
Themodel-freeapproachdoesnotincludeanyre-constructionoftheplayers'behaviour,beingpurelydata-driven.
Also,themethodisnotaimedatexplicitinteractions(suchaspasses)withinateam(cf.
[3]),butratheratimplicitinteractions,acrossteams,thatmaybedelayedand/orlong-ranged.
Theinteractionnetworkswereexempliedwithtwosub-typeshighlightingdifferent"slices"ofthedirectedinteractions:information-sinkandinformation-basediagrams.
Inaninformation-sinkdiagrameverynode(everyplayer)hasanincomingedge,whileinaninformation-basediagrameverynodehasanoutgoingedge.
Thesediagramswerecomputedfortwoexperimentalset-upsthatmatchedourteam(Gliders)againsttwowell-knownteams,Oxsy[18]andMarlik[19],showinginterestingplayer-to-playerinteractions,andpointingoutweakspotsandareastobeexploited.
Thefollow-uptacticalanalysisinvolvedcomputationofinformationtransferandstorage,andtwohypotheses.
TherstonerelatedpositiveinformationtransferfromplayersYtoplayersXasanindicationofresponsivenessofthelatter,suggestingtocomputerelativeresponsivenessbetweentheopposinglinesoftwoteams.
Thesecondhypothesisconnectedtheinformationstoragewithintheteamwiththeteam'srigidity,harmingtheuidityandtacticalrichnessoftheteam.
Thisrelationyieldedthescoreforrelativerigiditybetweentheopposingteams.
Bothmeasures,relativeresponsivenessandrigidity,werecorrelatedwiththegameresults,andtheobtainedobservationssup-portedthehypotheses.
Inaddition,theresultspointedtoimportantcouplingsthatwereparticularlyintense,andthemainareaswherethegameoutcomesweremostlydecided.
Thisapproachhasbeenfurthersuccessfullyappliedtoopponentmodellingandse-lectingthebestavailabletacticsinanopponent-specicway—thistopicisasubjectoffutureresearch.
WehopethattheproposedmethodswouldbeusefulnotonlyintheRoboCupleagues,butalsoinvariousanalysesofteamgames,whethervirtualorreal.
Acknowledgments.
ThisanalysiswascarriedoutusingGliders2013[20],afollowuponGliders2012[11]—asimulatedsoccerteamfortheRoboCupsoccer2Dsimu-lator[21].
Gliders2012andGliders2013reachedsemi-nalsinRoboCuptournamentsof2012and2013.
TheteamcodeiswritteninC++usingagent2d:thebasecodede-velopedbyAkiyamaetal.
[22],fragmentsofreleasedsourcecodeofMarlik[19],aswellasGliders'in-browserbasicsoccermonitor(GIBBS):alog-playerforviewing2DSimulationLeaguelogsoverwebbrowser[23].
WethankIvanDuong,EdwardMooreandJasonHeldfortheircontributiontoGlid-ers2012andGIBBS,aswellasDavidBuddenforhishelpwithdevelopingnewself-localisationmethod.
TeamlogowascreatedbyMatthewChadwick.
SomeoftheAu-thorshavebeeninvolvedwithRoboCupSimulation2Dinthepast,howeverthecodeoftheirpreviousteams(CyberoosandRoboLog,see,e.
g.
,[10,24])isnotusedinGliders.
References1.
Vilar,L.
,Araujo,D.
,Davids,K.
,Bar-Yam,Y.
:Scienceofwinningsoccer:Emergentpattern-formingdynamicsinassociationfootball.
JournalofSystemsScienceandComplexity26,73–84(2013)2.
Grabiner,D.
J.
:TheSabermetricManifesto,TheBaseballArchive3.
Fewell,J.
,Armbruster,D.
,Ingraham,J.
,Petersen,A.
,Waters,J.
:Basketballteamsasstrate-gicnetworks.
PLoSOne7(11),e47445(2012)12O.
M.
Cliffetal.
4.
Noda,I.
,Stone,P.
:TheRoboCupSoccerServerandCMUnitedClients:ImplementedInfras-tructureforMASResearch.
AutonomousAgentsandMulti-AgentSystems7(1-2),101–120(2003)5.
Riley,P.
,Stone,P.
,Veloso,M.
:Layereddisclosure:Revealingagents'internals.
In:Castel-franchi,C.
,Lesperance,Y.
(eds.
)IntelligentAgentsVII.
LNCS(LNAI),vol.
1986,pp.
61–72.
Springer,Heidelberg(2001)6.
Stone,P.
,Riley,P.
,Veloso,M.
:Deningandusingidealteammateandopponentmodels.
In:Proc.
ofthe12thAnnualConf.
onInnovativeApplicationsofArticialIntelligence(2000)7.
Butler,M.
,Prokopenko,M.
,Howard,T.
:FlexiblesynchronisationwithinRoboCupenviron-ment:Acomparativeanalysis.
In:Stone,P.
,Balch,T.
,Kraetzschmar,G.
K.
(eds.
)RoboCup2000.
LNCS(LNAI),vol.
2019,pp.
119–128.
Springer,Heidelberg(2001)8.
Reis,L.
P.
,Lau,N.
,Oliveira,E.
C.
:Situationbasedstrategicpositioningforcoordinatingateamofhomogeneousagents.
In:Hannebauer,M.
,Wendler,J.
,Pagello,E.
(eds.
)Reactiv-ityandDeliberationinMAS.
LNCS(LNAI),vol.
2103,pp.
175–197.
Springer,Heidelberg(2001)9.
Prokopenko,M.
,Wang,P.
:Relatingtheentropyofjointbeliefstomulti-agentcoordination.
In:Kaminka,G.
A.
,Lima,P.
U.
,Rojas,R.
(eds.
)RoboCup2002.
LNCS(LNAI),vol.
2752,pp.
367–374.
Springer,Heidelberg(2003)10.
Prokopenko,M.
,Wang,P.
:Evaluatingteamperformanceattheedgeofchaos.
In:Polani,D.
,Browning,B.
,Bonarini,A.
,Yoshida,K.
(eds.
)RoboCup2003.
LNCS(LNAI),vol.
3020,pp.
89–101.
Springer,Heidelberg(2004)11.
Prokopenko,M.
,Obst,O.
,Wang,P.
,Held,J.
:Gliders2012:Tacticswithaction-dependentevaluationfunctions.
In:RoboCup2012SymposiumandCompetitions:TeamDescriptionPapers,MexicoCity,Mexico(June2012)12.
Lizier,J.
T.
,Prokopenko,M.
,Zomaya,A.
Y.
:Localinformationtransferasaspatiotemporallterforcomplexsystems.
PhysicalReviewE77(2),026110(2008)13.
Lizier,J.
T.
,Prokopenko,M.
,Zomaya,A.
Y.
:Informationmodicationandparticlecollisionsindistributedcomputation.
Chaos20(3),037109(2010)14.
Lizier,J.
T.
,Prokopenko,M.
,Zomaya,A.
Y.
:Coherentinformationstructureincomplexcom-putation.
TheoryinBiosciences131,193–203(2012)15.
Lizier,J.
T.
,Prokopenko,M.
,Zomaya,A.
Y.
:Localmeasuresofinformationstorageincom-plexdistributedcomputation.
InformationSciences208,39–54(2012)16.
Schreiber,T.
:Measuringinformationtransfer.
Phys.
Rev.
Lett.
85(2),461–464(2000)17.
Wang,X.
R.
,Miller,J.
M.
,Lizier,J.
T.
,Prokopenko,M.
,Rossi,L.
F.
:Quantifyingandtracinginformationcascadesinswarms.
PLoSOne7(7),e40084(2012)18.
Marian,S.
,Luca,D.
,Sarac,B.
,Cotarlea,O.
:Oxsy2011teamdescriptionpaper.
In:RoboCup2011SymposiumandCompetitions:TeamDescriptionPapers,Istanbul(2011)19.
Tava,A.
,Nozari,N.
,Vatani,R.
,Youse,M.
R.
,Rahmatinia,S.
,Pirdir,P.
:MarliK2012Soccer2DSimulationTeamDescriptionPaper.
In:RoboCup2012SymposiumandCompe-titions:TeamDescriptionPapers,MexicoCity,Mexico(June2012)20.
Prokopenko,M.
,Obst,O.
,Wang,P.
,Budden,D.
,Cliff,O.
:Gliders2013:TacticalAnalysiswithInformationDynamics.
In:RoboCup2013SymposiumandCompetitions:TeamDe-scriptionPapers,Eindhoven(June2013)21.
Chen,M.
,Dorer,K.
,Foroughi,E.
,Heintz,F.
,Huang,Z.
,Kapetanakis,S.
,Kostiadis,K.
,Kummeneje,J.
,Murray,J.
,Noda,I.
,Obst,O.
,Riley,P.
,Steffens,T.
,Wang,Y.
,Yin,X.
:UsersManual:RoboCupSoccerServer—forSoccerServerversion7.
07andLater(February2003)22.
Akiyama,H.
:Agent2DBaseCode(2010),http://www.
rctools.
sourceforge.
jp23.
Moore,E.
,Obst,O.
,Prokopenko,M.
,Wang,P.
,Held,J.
:Gliders2012:Developmentandcompetitionresults.
CoRRabs/1211.
3882(2012)24.
Obst,O.
,Boedecker,J.
:FlexiblecoordinationofmultiagentteambehaviorusingHTNplan-ning.
In:Bredenfeld,A.
,Jacoff,A.
,Noda,I.
,Takahashi,Y.
(eds.
)RoboCup2005.
LNCS(LNAI),vol.
4020,pp.
521–528.
Springer,Heidelberg(2006)