Improving Offensive Performance through Opponent Modeling KennardLaviers GitaSukthankar MatthewMolineaux DavidW.Aha SchoolofEECS SchoolofEECS KnexusResearch NCARAI U.ofCentralFlorida U.ofCentralFlorida Springfield,VA NavalResearchLab Orlando,FL Orlando,FL matthew.molineaux@ Washington,DC [email protected] [email protected] knexusresearch.com [email protected] Abstract Althoughintheoryopponentmodelingcanbeusefulinany adversarialdomain,inpracticeitisbothdifficulttodoaccu- rately and to use effectively to improve game play. In this paper,wepresentanapproachforonlineopponentmodeling andillustratehowitcanbeusedtoimproveoffensiveperfor- manceintheRush2008footballgame. Infootball,teambe- haviorshaveanobservablespatio-temporalstructure,defined bytherelativephysicalpositionsofteammembersovertime; wedemonstratethatthisstructurecanbeexploitedtorecog- nizefootballplaysataveryearlystageoftheplayusingasu- pervisedlearningmethod. Basedontheteams’playhistory, oursystemevaluatesthecompetitiveadvantageofexecuting aplayswitchbasedonthepotentialofotherplaystoincrease theyardagegainedandthesimilarityofthecandidateplays to the current play. In this paper, we investigate two types ofplayswitches: 1)wholeteamand2)subgroupswitching. Bothtypesofplayswitchesimproveoffensiveperformance, Figure 1: Screenshot of the Rush 2008 football simulator. butbyonlymodifyingthebehaviorofakeysubgroupofof- Theoffenseteam(showninred)isusingtheplaysplit8and fensiveplayers,weimproveontheyardagegained. being countered by the defense (shown in blue) using a 31 formation(variant1). Introduction By accessing the play history of your opponent, it is pos- sible to glean critical insights about future plays. This was (militaryorathletic), teambehaviorsoftenhaveanobserv- recently demonstrated at a soccer match by an innovative, ablespatio-temporalstructure,definedbytherelativephys- well-prepared goalkeeper who used his iPod to review a ical positions of team members. This structure can be ex- videoplayhistoryoftheplayertakingapenaltykick;iden- ploited to perform behavior recognition on traces of agent tifying the player’s tendency to kick to the left allowed the activityovertime. Thispaperdescribesamethodforrecog- goalkeeper to successfully block the shot (Bennett 2009). nizingdefensiveplaysfromspatio-temporaltracesofplayer Althoughplayhistorycanbeausefulsourceofinformation, movement in the Rush 2008 football game (see Figure 1) itisdifficulttoutilizeeffectivelyinasituationwithalarge andusingthisinformationtoimproveoffensiveplay. numberofmulti-agentinteractions.Opponentmodelingcan TosucceedatAmericanfootball, ateammustbeableto bedividedintothreecategories: 1)onlinetracking2)online successfullyexecuteclosely-coordinatedphysicalbehavior. strategyrecognitionand3)off-linereview. Inonlinetrack- Toachievethistightphysicalcoordination,teamsrelyupon ing, immediatefutureactionsofindividualplayers(passes, apre-existingplaybookofoffensivemaneuverstomovethe feints)arepredicted,whereasinonlinestrategyrecognition, balldownthefieldanddefensivestrategiestocountertheop- the observer attempts to recognize the high-level strategy posing team’s attempts to make yardage gains. Rush 2008 usedbytheentireteam. Inofflinereview,generalstrengths, simulatesamodifiedversionofAmericanfootball;playsin weaknesses, and tendencies are identified in an offline set- Rusharecomposedofastartingformationandinstructions tingandusedaspartofthetraining/learningregimen. foreachplayerintheformation. Theseinstructionsaresim- This paper addresses the problem of online strategy ilartoaconditionalplanandincludechoicepointswherethe recognitioninadversarialteamgames. Inphysicaldomains playerscanmakeindividualdecisionsaswellaspre-defined Copyright(cid:13)c 2009,AssociationfortheAdvancementofArtificial behaviorsthattheplayerexecutestothebestofitsphysical Intelligence(www.aaai.org).Allrightsreserved. capability. Rush2008wasdevelopedfromtheopensource Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2009 2. REPORT TYPE 00-00-2009 to 00-00-2009 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER Improving Offensive Performance through Opponent Modeling 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION Knexus Research Corp,9120 Beachway Lane,Springfield,VA,22153 REPORT NUMBER 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES To appear in Proceedings of the Fifth Conference on Artificial Intelligence and Interactive Digital Entertainment. Stanford, CA: AAAI Press 2009 14. ABSTRACT Although in theory opponent modeling can be useful in any adversarial domain, in practice it is both difficult to do accurately and to use effectively to improve game play. In this paper, we present an approach for online opponent modeling and illustrate how it can be used to improve offensive performance in the Rush 2008 football game. In football, team behaviors have an observable spatio-temporal structure, defined by the relative physical positions of team members over time we demonstrate that this structure can be exploited to recognize football plays at a very early stage of the play using a supervised learning method. Based on the teams? play history our system evaluates the competitive advantage of executing a play switch based on the potential of other plays to increase the yardage gained and the similarity of the candidate plays to the current play. In this paper, we investigate two types of play switches: 1) whole team and 2) subgroup switching. Both types of play switches improve offensive performance but by only modifying the behavior of a key subgroup of offensive players, we improve on the yardage gained. 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE Same as 7 unclassified unclassified unclassified Report (SAR) Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 Rush 2005 game, which is similar in spirit to Tecmo Bowl field is 100 yards by 63 yards. The game’s objective is to andNFLBlitz(Rush20052005). out-score the opponent, where the offense (i.e., the team Although there have been other studies examining the with possession of the ball), attempts to advance the ball problemofrecognizingcompletedfootballplays,wepresent fromthelineofscrimmageintotheiropponent’sendzone. resultsonrecognizingfootballplaysonlineatanearlystage In a full game, the offensive team has four attempts to get of play, and demonstrate a mechanism for exploiting this afirstdownbymovingtheball10yardsdownthefield. If knowledge to improve a team’s offense. Our system eval- the ball is intercepted or fumbled, ball possession transfers uates the competitive advantage of executing a play switch tothedefensiveteam. basedonthepotentialofotherplaystoimprovetheyardage gained and the similarity of the candidate plays to the cur- rentplay.Ourplayswitchselectionmechanismoutperforms boththebuilt-inoffenseandagreedyyardage-basedswitch- ingstrategy.Calculatingtherelativesimilarityofthecurrent play compared to the proposed play is shown to be a nec- essary step to reduce confusion on the field and effectively boostperformance. Additionallyweinvestigatedtheutility Provs23 Powervs31 Splitvs2222 oflimitingtheplayswitchtoasmallsubgroupofplayers;by onlymodifyingtheactionsofsmallsubgroupofkeyplayers, Figure2: Threeoffensiveanddefensiveconfigurations. Of- wecanimproveonthetotalteamswitch. fensiveplayersareshowninwhiteandthedefenseinblue. RelatedWork ARushplayiscomposedof(1)astartingformationand Previous work on team behavior recognition has been pri- (2)instructionsforeachplayerinthatformation. Aforma- marilyevaluatedwithinathleticdomains,includingAmeri- tion is a set of (x,y) offsets from the center of the line of canfootball(IntilleandBobick1999),basketball(Bhandari scrimmage. Bydefault,directionsforeachplayerconsistof et al. 1997; Jug et al. 2003), and Robocup soccer simula- (a)anoffset/destinationpointonthefieldtorunto,and(b) tions(RileyandVeloso2000;2002;Kuhlmannetal. 2006). abehaviortoexecutewhentheygetthere. Playinstructions To recognize athletic behaviors, researchers have exploited are similar to a conditional plan and include choice points simple region-based (Intille and Bobick 1999) or distance- wheretheplayerscanmakeindividualdecisionsaswellas based (Riley and Veloso 2002) heuristics to build accurate, pre-definedbehaviorsthattheplayerexecutestothebestof but domain-specific classifiers. For instance, based on the theirphysicalcapability. Rushincludesthreeoffensivefor- premisethatallbehaviorsalwaysoccuronthesameplaying mations(power,pro,andsplit)andfourdefensiveones(23, field with a known number of entities, it is often possible 31,2222,2231)2. Eachformationhaseightdifferentplays to divide the playing field into grids or typed regions (e.g., (numbered 1-8) that can be executed from that formation. goal,scrimmageline)thatcanbeusedtoclassifyplayerac- Offensive plays typically include a handoff to the running tions.Incontrast,wetrainourclassifiersonrawobservation back/fullback or a pass executed by the quarterback to one tracesanddonotrelyonafield-basedmarkersystem. ofthereceivers,alongwithinstructionsforarunningpattern In Robocup, there has been some research on team in- tobefollowedbyallthereceivers. tentrecognitiongearedtowardstheRobocupcoachcompe- tition. Techniques have been developed to extract specific PlayRecognitionusingSVM information, such as home areas (Riley et al. 2002), op- Inthispaperwefocusonintentrecognitionfromtheview- ponent positions during set-plays (Riley and Veloso 2002), pointoftheoffense: givenaseriesofobservations,ourgoal andadversarialmodels(RileyandVeloso2000), fromlogs is to recognize the defensive play as quickly as possible ofRobocupsimulationleaguegames. Thisinformationcan in order to maximize our team’s ability to intelligently re- be utilized by the coach agent to improve the team’s scor- spondwiththebestoffense. Thus,theobservationsequence ingperformance. Forinstance,informationaboutopponent grows with time unlike in standard offline activity recogni- agent home areas can be used triggers for coaching advice tion where the entire set of observations is available. We andfordoing“formation-basedmarking”,inwhichdifferent approachtheproblembytrainingaseriesofmulti-classdis- teammembersareassignedtotrackmembersoftheoppos- criminative classifiers, each of which is designed to handle ing team. However, the focus of the coaching agents is to observationsequencesofaparticularlength. Ingeneral,we improveperformanceofteamsinfuturegames; oursystem expectthattheearlyclassifiersshouldbelessaccuratesince immediatelytakesactionontherecognizedplaytoevaluate theyareoperatingwithashorterobservationvectorandbe- possibleplayswitches. cause the positions of the players have deviated little from theinitialformation. RushFootball We perform this classification using support vector ma- Football is a contest of two teams played on a rectangular chines (Vapnik 1998). Support vector machines (SVM) field that is bordered on lengthwise sides by an end zone. are a supervised binary classification algorithm that have Unlike American football, Rush teams only have 8 players been demonstrated to perform well on a variety of pattern on the field at a time out of a roster of 18 players. and the classificationtasks,particularlywhenthedimensionalityof the data is high (as in our case). Intuitively the support currentstartingconfigurationandtimestep. Anobservation vector machine projects data points into a higher dimen- vector of the correct length is generated (this can be done sional space, specified by a kernel function, and computes incrementally during game play) and fed to the multi-class a maximum-margin hyperplane decision surface that sepa- SVM. The output of the intent recognizer is the system’s ratesthetwoclasses. Supportvectorsarethosedatapoints best guess (at the current time step) about the opponent’s that lie closest to this decision surface; if these data points choice ofdefensive playand can helpus toselect the most were removed from the training data, the decision surface appropriateoffense,asdiscussedbelow. would change. More formally, given a labeled training set Table 1 summarizes the experimental results for differ- {(x ,y ),(x ,y ),...,(x ,y )}, where x ∈ (cid:60)N is a fea- ent lengths of the observation vector (time from start of 1 1 2 2 l l i ture vector and y ∈ {−1,+1} is its binary class label, an play), averaging classification accuracy across all starting i SVMrequiressolvingthefollowingoptimizationproblem: formation choices and defense choices. We see that at the earliest timestep, our classification accuracy is at the base- l 1 (cid:88) line but jumps sharply near perfect levels at t = 3. This min wTw+C ξ w,b,ξ 2 i strongly confirms the feasibility of accurate intent recogni- i=1 tion in Rush, even during very early stages of a play. At constrainedby: t = 2, there is insufficient information to discriminate be- tweenoffenseplays(perceptualaliasing),howeverbyt=3, yi(wTφ(xi)+b) ≥ 1−ξi, thepositionsoftheoffensiveteamaredistinctiveenoughto ξ ≥ 0. bereliablyrecognized. i The function φ(.) that maps data points into the higher di- OffensivePlaySwitches mensionalspaceisnotexplicitlyrepresented; rather, aker- Toimproveoffensiveperformance,oursystemevaluatesthe nelfunction,K(x ,x )≡φ(x )φ(x ),isusedtoimplicitly i j i j competitive advantage of executing a play switch based on specifythismapping. Inourapplication,weusethepopular 1)thepotentialofotherplaystoimprovetheyardagegained radialbasisfunction(RBF)kernel: and 2) the similarity of the candidate plays to the current K(x ,x )=exp(−γ||x −x ||2),γ >0. play. First, we train a set of SVM models to recognize de- i j i j fensiveplaysataparticulartimehorizonasdescribedinthe Several extensions have been proposed to enable SVMs previous section; this training data is then used to identity to operate on multi-class problems (with k rather than 2 promisingplayswitches. Aplayswitchisexecuted: classes),suchasone-vs-all,one-vs-one,anderror-correcting 1. after the defensive play has been identified by the SVM output codes. We employ a standard one-vs-one voting classifier; schemewhereallpairwisebinaryclassifiers,k(k−1)/2 = 28foreverymulti-classprobleminourcase,aretrainedand 2. ifthereisastrongeralternateplaybasedontheyardage the most popular class is selected. When multiple classes historyofthatplayvs.thedefense; receivethehighestvote,weselectthewinningonewiththe 3. ifthecandidateplayissufficientlysimilartothecurrent lowest index; the benefit of this approach is that classifica- playtobefeasibleforimmediateexecution. tion is deterministic but it can bias our classification in fa- vor of lower-numbered plays. For a real game system, we To determine whether to execute the play switch for a par- wouldemployarandomizedtie-breakingstrategy. Manyef- ticularcombinationofplays,theagentconsidersN,theset ficientimplementationsofSVMsarepubliclyavailable;we of all offensive plays shown to gain more than a threshold useLIBSVM(ChangandLin2001). (cid:15) value. The agent then selects Min(n ∈ N), the play in We train our classifiers using a collection of simulated thelistmostlikethecurrentplayforeachplayconfiguration games in Rush collected under controlled conditions: 40 andcachesthepreferredplayinalookuptable. instances of every possible combination of offense (8) and When a play is executed, the agent will use all observa- defense plays (8), from each of the 12 starting formation tions up to and including observation 3 to determine what configurations. Since the starting configuration is known, playthedefenseisexecutingbeforeperformingalookupto each series of SVMs is only trained with data that could determine the play switch to make. The process is ended beobservedstartingfromitsgivenconfiguration. Foreach with execution of a change order to all members of the of- configuration, we create a series of training sequences that fensive team. Calculating the feasibility of the play switch accumulates spatio-temporal traces from t = 0 up to t ∈ based on play similarity is a crucial part of improving the {2,...,10}timesteps. AmulticlassSVM(i.e.,acollection team’s performance; in the results section, we evaluate our of 28 binary SVMs) is trained for each of these cases. Al- similarity-based play switch mechanism vs. a greedy play though the aggregate number of binary classifiers is large, switchingalgorithmthatfocusessolelyonthepotentialfor each classifier only employs a small fraction of the dataset yardagegained. andisthereforeefficient(andhighlyparalellizable). Cross- PlaySimilarityMetric validationwasusedtotunetheSVMparameters(C andσ) foralloftheSVMs. To calculate play similarities, we create a feature matrix Classificationattestingtimeisveryfastandproceedsas for all offensive formation/play combinations based on the follows. WeselectthemulticlassSVMthatisrelevanttothe trainingdata. Table1: Playrecognitionresults(accuracyoverallplaycombinations) t=2 3 4 5 6 7 8 9 10 12.50 96.88 96.87 96.85 96.84 96.87 96.89 96.83 96.81 ThefeaturescollectedforeachathleteAare history (based on earlier observation) of scoring the most yardage. This process is accomplished for every offensive Max(X): TherightmostpositiontraveledtobyA play formation against every defensive play formation Max(Y): ThehighestpositiontraveledtobyA and play combination. When the agent is constructing Min(X): TheleftmostpositiontraveledtobyA the lookup table and needs to determine the most similar play from a list, given current play i, it calls the method, Min(Y): ThelowestpositiontraveledtobyA min(O D M )whichreturnsthemostsimilarplay. β αp i Mean(X): = PNi=−01Xi N Mean(Y): = PNi=−01Yi ImprovingtheOffense N Our algorithm for improving Rush offensive play has two Median(X): = Sort(X) i/2 mainphases, apreprocessstagewhichyieldsaplayswitch Median(Y): = Sort(Y) lookuptableandanexecutionstagewherethedefensiveplay i/2 is recognized and the offense responds with an appropriate FirstToLastAngle: Angle from starting point (x1,y1), to (cid:16) (cid:17) playswitchforthatdefensiveplay. AsdescribedinSection endingpoint(x2,y2),isdefinedasatan (cid:52)y wetrainasetofSVMclassifiersusing40instancesofevery (cid:52)x possible combination of offense (8) and defense plays (8), Start Angle: Angle from the starting point (x ,y ) to 0 0 fromeachofthe12startingformationconfigurations. This (x ,y ),definedasatan(cid:0)y(cid:1) 1 1 x stageyieldsasetofmodelsusedforplayrecognitionduring End Angle: Anglefromthestartingpoint(x ,y )to thegame. Next,wecalculateandcacheplayswitchesusing n−1 n−1 (cid:16) (cid:17) thefollowingprocedure: (x ,y ),definedasatan (cid:52)y n n (cid:52)x Step1: Collect data by running the RUSH 2008 football (cid:16) (cid:17) Total Angle: =(cid:80)N−1atan yi+1−yi simulator50timesforeveryplaycombination. i=0 xi+1−xi Step2: Createyardagelookuptablesforeachplaycombi- Total Path Distance: =(cid:80)N−1(cid:16)(cid:112)2 x 2+y 2(cid:17) nation.Thisinformationaloneisinsufficienttodetermine i=0 i i how good a potential play is to perform the play switch Feature set F for a given play c contains all the features actionon. Thetransitionplaymustresembleourcurrent foreachoffensiveplayerintheplayandisdescribedas offensiveplayortheoffensiveteamwillspendtoomuch −→ timeretracingstepsandperformverypoorly. F ={A ∪A ∪A ∪···∪A } c c1 c1 c2 c8 Step3: Create feature matrix for all offensive forma- These features are similar to the ones used in (Rubine tion/play combinations using the probabilistic trace rep- 1991) and more recently, by (Wobbrock et al. 2007) to resentation. matchpentrajectoriesinsketch-basedrecognitiontasks,but Step4: Create the final play switch lookup table based on generalizedtohandlemulti-playertrajectories. Tocompare boththeyardageinformationandtheplaysimilarity. playsweusethesumoftheabsolutevalueofthedifferences (L norm) between each feature F . This information is To create the play switch lookup table, the agent first 1 ci used to build a similarity matrix M for each possible of- extracts a list of offensive plays L given the requirement ij fensiveplaycombinationasdefinedbelow. yards(Li) > (cid:15) where (cid:15) is the smallest yardage gained in which the agent does not consider changing the cur- ‚‚‚−F→c‚‚‚−1 rent offensive play to another. We used (cid:15) = 1.95 based (cid:88) −→ on a quadratic polynomial fit of total yardage gained in M = ∆F ij c 6 tests with (cid:15) = {MIN,1.1,1.6,2.1,2.6,MAX} where c=0 MIN is small enough no plays are selected to change and i,j =1...8 MAX whereallplaysareselectedforchangetothehighest yardage play with no similarity comparison. Second, from There is one matrix M for each offensive formation thelistLfindtheplaymostsimilar(smallestvalueinthema- O , where β = {pro, power, split} are the offensive β trix)toourcurrentplayiusingMin(O D M )andaddit formations. Defensive formation/play combinations are β αp i tothelookupfile. indicated by D , where α = {23, 31, 2222, 2231} and αp During execution, the offense uses the following proce- p represents plays 1..8. M for a specific play configuration dure: is expressed as O D M , given i (1...8) is our current β αp i offensive play. The purpose of this algorithm is to find a 1. Ateachobservationlessthan4,collectmovementtraces value j (play) most similar to i (our current play), with a foreachplay. 2. Atobservation3,useLIBSVMwiththecollectedmove- menttracesandpreviouslytrainedSVMmodelstoiden- tifythedefensiveplay. 3. Accessthelookupfiletofindbest(i)forourcurrentplay i. 4. Send a change order command to the offensive team to changetoplaybest(i). However it is not necessary (or always desirable) to change all of the players to the new play. We also inves- tigated the performance of subgroup switching, modifying the play of small group of key players while leaving the remaining players alone. By segmenting the team in this fashionweareabletoinessencecombinetwoplayswhich hadpreviouslybeenidentifiedasaliketoeachotherwithre- Figure4:Comparisonofplayswitchselectionmethods.Our gardtospatio-temporaldata,butdifferentinregardstoyards play switch method (shown in red) outperforms both base- gained.Thefootballoffensiveteamlendsitselftothreemain line Rush offense (blue) and a greedy play switch metric groups based on domain knowledge of football. Group 1 (green). contains the QB, RB, and FB; group 2 has LG, C and RG; andgroup3consistsoftheremainingplayersLWR,RWR, RTE,andLTE. Figure 3 is a good example of a successful merging of twoplaystoproduceasuperiorplaygiventhisdefense. The green line represents the average yardage gained. The left image is the most likely path of the baseline case (a run- ningplaywhichyieldslittleyardageonaverage). Themid- dleimageisthemostlikelyexecutiontraceproducedbythe total play switch method. The play produced by the total playswitchwasnotmuchmoresuccessfulthanthebaseline case;howeverwhenonlyGroup1(QB,RB,FB)ismodified thesuccessoftheplayincreasesgreatlyandthenewplayis showntobeverycoordinatedandeffective. EmpiricalEvaluation The algorithm was tested using the RUSH 2008 simulator Figure5: Theplay-yardagegainoverbaselineRushoffense for ten plays on each possible play configuration in three yieldedbyourplayswitchstrategy. separate trials. We compared our play switch model (us- ing the yardage threshold (cid:15) = 1.95 as determined by the quadratic fit) to the baseline Rush offense and to a greedy about .2 to .4 yards more than the gains in the baseline play switch strategy ((cid:15) = MAX) based solely on the sample. In 6 we see all the split configurations do quite yardage. well; this is unsurprising given our calculations of the best Overall, the average performance of the offense went response. However,whenthethresholdisnotinuseandthe from2.82 yardsper playto3.65 yardsper play((cid:15) = 1.95) plays are allowed to change regardless of current yardage, with an overall increase of 29%, ±1.5% based on sam- the results are drastically reduced. The reason seems to be pling of three sets of ten trials. An analysis of each of the associated player miscoordinations accidentally induced formation combinations (Figure 6) shows the yardage gain by the play switch; by maximizing the play similarity varies from as much as 100% to as little as 0.1%. Over- simultaneously, the possibility of miscoordinations is all, performance is consistently better for every configura- reduced. Figure 5 shows yardage gained by the best play tiontested. Inallcases,thenewaverageyardageisover2.3 switch strategy over the Rush baseline offense. Power yards per play with no weak plays as seen in the baseline. vs.23experiencesthegreatestenhancementandSplitvs.31 Forexample,Powervs.23(1.4averageyardsperplay)and the least. It is interesting to note Split formations in the Power vs. 2222 (1.3 average yards per play). Results with baseline performed best and improved the least while the (cid:15) = MAX clearly shows simply changing to the greatest Power formations performed the worst in the baseline and yardage generally results in poor performance from the of- improvedthemost. Thisindicatesaninverselyproportional fense. expectedgainbythealgorithm. Powervs.23isdramaticallyboostedfromabout1.5yards to about 3 yards per play, doubling yards gained. Other To evaluate the subgroup switching, we ran the simula- combinations, such as Split vs. 23 and Pro vs. 32 already tion over all three groups and compared them to the base- scored good yardage and improved less dramatically at lineyardagegainedandtheresultsoftotalplayswitch. Test Figure3: Subgroupswitching References iPodVideo“Saves”theDayforManchesterUnited,2009. http://www.jeffbennett.org/2009/03/ ipod-video-saves-the-day-for-manchester-united/. I. Bhandari, E. Colet, J. Parker, Z. Pines, R. Pratap, and K.Ramanujam. AdvancedScout: Dataminingandknowl- edgediscoveryinNBAdata. DataMiningandKnowledge Discovery,1(1):121–125,1997. C.-C.ChangandC.-J.Lin. LIBSVM:alibraryforsupport vector machines, 2001. Software available at http:// www.csie.ntu.edu.tw/˜cjlin/libsvm. Figure6: Comparisonofsubgroupandtotalplayswitching S. Intille and A. Bobick. A framework for recognizing multi-agent action from visual evidence. In Proceedings ofNationalConferenceonArtificialIntelligence,1999. results clearly indicated the best subgroup switch (consis- M. Jug, J. Pers, B. Dezman, and S. Kovacic. Trajectory tentlyGroup1)producedgreatergainsthanthetotalchange, based assessment of coordinated human activity. In Pro- whichstillperformedbetterthanthebaseline. Figure2isa ceedingsoftheInternationalConferenceonComputerVi- side-by-side comparison of the results. We also compared sionSystems(ICVS),2003. the results to the yardage gained if the team had initially chosen the best response play (the play that on average re- G.Kuhlmann,W.Knox,andP.Stone. Knowthineenemy: sultsinthegreatestyardagegain)forthatformation. Early AchampionRoboCupcoachagent. InProceedingsofNa- play recognition combined with subgroup switching yields tionalConferenceonArtificialIntelligence,2006. thebestresults,assumingnooracleknowledgeoftheother P. Riley and M. Veloso. On behavior classification in team’sintentionspriortorun-time. adversarial environments. In L. Parker, G. Bekey, and J. Barhen, editors, Distributed Autonomous Robotic Sys- Conclusion tems4.Springer-Verlag,2000. P. Riley and M. Veloso. Recognizing probabilistic op- In this paper, we present an approach for early, accurate ponent movement models. In A. Birk, S. Coradeschi, recognition of defensive plays in the Rush 2008 football andS.Tadorokoro,editors,RoboCup-2001: RobotSoccer simulator. We demonstrate that a multi-class SVM classi- WorldCupV.SpringerVerlag,2002. fier trained on spatio-temporal game traces can enable the P. Riley, M. Veloso, and G. Kaminka. An empirical offensetocorrectlyanticipatethedefense’splaybythethird study of coaching. In H. Asama, T. Arai, T. Fukuda, timestep. Usingthisinformationaboutthedefense’sintent, andT.Hasegawa,editors,DistributedAutonomousRobotic our system evaluates the competitive advantage of execut- Systems5.Springer-Verlag,2002. ing a play switch based on the potential of other plays to D. Rubine. Specifying gestures by example. Computer improve the yardage gained and the similarity of the can- Graphics,Volume25,Number4,pages329–337,1991. didate plays to the current play. Our play switch selec- Rush, 2005. http://sourceforge.net/ tionmechanismoutperformsboththebuilt-inRushoffense projects/rush2005/. and a greedy yardage-based switching strategy, increasing yardage while avoiding the miscoordinations accidentally V.Vapnik.StatisticalLearningTheory.Wiley&Sons,Inc, inducedbythegreedystrategyduringthetransitionfromthe 1998. oldplaytothenewone. Additionally, wedemonstratethat J. Wobbrock, D. Wilson, and L. Yang. Gestures without limitingtheplayswitchtoasubgroupofkeyplayersfurther libraries,toolkitsortraining:a$1recognizerforuserinter- improvesperformance. faceprototypes. InSymposiumonUserInterfaceSoftware and, Proceedingsofthe20thannualACMsymposiumon Userinterfacesoftwareandtechnology,2007.