Transcript 슬라이드 1
지능형 에이전트 -게임에서의 활용, CIG Competition- Agent Applications • Where are agents used? – – – – – – – Robotics On the web Movie and game production Scientific simulations Defense applications Distributed computing (e.g. XGrid) Mobile applications • Why are agents useful? – Software engineering. • Modularity, abstraction, complexity, management, etc. – – – – Match many problem domains Good surrogates for humans Cognitive and social models Provide intelligent behavior • Where artificial intelligence and software engineering meet 1/34 Agent Applications 1. 2. 3. 4. 5. 6. Automated Office Unified Messaging Multimodal Maps CommandTalk ATIS-Web Spoken Dialog Summarization 7. Agent Development Tools 8. InfoBroker 9. Rental Finder 10. InfoWiz Kiosk 11. Multi-Robot Control 12. MVIEWS Video Tools 13. MARVEL 14. SOLVIT 15. Surgical Training 16. Instant Collaboration 17.Crisis Response 18. WebGrader 19. Speech Translation 20-25+ ... 2/34 Interfacing Agents • Talking heads – Naturalistic figures – Many possible platforms: • Web, mobile device, set-top box – Applications • News reading, signing, interactive digital TV programme guide • Electronic Virtual Assistants in e-commerce • Vandrea – Thin client solution, that reads news scripts live from ITN 3/34 Microsoft Agent • Components – Toolbox of technologies • Speech rec, text-to-speech – Scripting language • Controls animation at high-level • Good but rigid – Pre-designed characters • Rather cutesy, but you can create your own – Only viewable with Active X • Microsoft Persona Project – The project is developing the technologies required to produce conversational assistants - lifelike animated characters that interact with a user in a natural spoken dialogue – The work is built upon the Whisper speaker-independent continuous speech recognition system and a broad coverage English understanding system, both also developed at Microsoft Research 4/34 Web Search 5/34 Recommendation 6/34 Work Assistant 7/34 Agents in Defense • Used to represent human military operators – Fighter Pilots (enemy and friendly), commanders, sensor operators etc • Training • Human factors research • Military operations research 8/34 Game AI, Bots and Agents 9/34 Nintendogs 10/34 Massive (www.massivesoftware.com) 11/34 Introduction to Artificial Intelligence (AI) • Many applications for AI – Computer vision, natural language processing, speech recognition, search … • But games are some of the more interesting • Opponents that are challenging, or allies that are helpful – Unit that is credited with acting on own • Human-level intelligence too hard – But under narrow circumstances can do pretty well (ex: chess and Deep Blue) – For many games, often constrained (by game rules) • Artificial Intelligence (around in CS for some time) 12/34 AI for CS different than AI for Games • Must be smart, but purposely flawed – Loose in a fun, challenging way • No unintended weaknesses – No “golden path” to defeat – Must not look dumb • Must perform in real time (CPU) • Configurable by designers – Not hard coded by programmer • “Amount” and type of AI for game can vary – RTS needs global strategy, FPS needs modeling of individual units at “footstep” level – RTS most demanding: 3 full-time AI programmers – Puzzle, street fighting: 1 part-time AI programmer 13/34 Goals • Games are entertainment • Important that things behave naturally – Not necessarily perfect – “things’ are not always creature • Follow(the game’s) natural laws – And avoid cheating • Characters should be aware 14/34 Game categories • Role Playing Game(RPG, MMORPG) • First Person(Third Person) games • Sports games • Simulation games • Adventure games • Classic Strategy game • Fighting games •… 15/34 History 1-4 • 1960’s – First computer games • SpaceWar(for two human players)(1962) • Board games(e.g. chess) againt the machine • 1970’s – – – – – Pong(first public computer game?)(1972) First computer controlled opponent in arcade games Space Invaders(1978) Predefined patterns “AI” takes 1-2% of CPU 16/34 History 2-4 • 1980’s – Pac-Man(1980) • Opponents with personality – A computer beats a master chess player(1983) – First fight games – Adventure games • Dungeon, Zork, … – First MORPG(MUD) 17/34 History 3-4 • 1990’s – – – – – FPS and RTS games Games about / with evolution and learning (Creatures, Black and White) Deep Blue beats Kaparov(1997) Graphic cards take the load off the CPU AI take 10-35% of CPU 18/34 History 4-4 • 2000– Computer games is a BIG industry • Games sell for about 25 billon USD per year • Market grows with 16% per year • A game project: 2 years, 8-15 million USD – – – – Less cheating in AI Characters are more aware Characters collaborate better Focus shift from graphics towards AI 19/34 Game Agents • Most AI focuses around game agent – think of agent as NPC, enemy, ally or neutral • Loops through: sense-think-act cycle – Acting is event specific, so talk about sense and think first, then a bit on act Sense Think Act 20/34 Game Agents – Sensing (1 of 2) • Gather current world state: barriers, opponents, objects, … • Needs limitations: avoid “cheating” by looking at game data – Typically, same constraints as player (vision, hearing range, etc.) • Vision – Can be quite complicated (CPU intensive) to test visibility (ie- if only part of an object visible) – Compute vector to each object • Check magnitude (ie- is it too far away?) • Check angle (dot product) (ie- within 120° viewing angle?) • Check if obscured. Most expensive, so do last. Game Agents – Sensing (2 of 2) • Hearing – Ex- tip-toe past, enemy doesn’t hear, but if run past, enemy hears (stealth games, like Thief) – Implement as event-driven • When player performs action, notify agents within range – Rather than sound reflection (complicated) usually distance within bounded area • Can enhance with listen attributes by agent (if agent is “keen eared” or paying attention) • Communication – Model sensing data from other agents – Can be instant (ie- connected by radio) – Or via hearing (ie- shout) • Reaction times – Sensing may take some time (ie- don’t have agent react to alarm instantly, seems unrealistic) – Build in delay. Implement with simple timer. Game Agents – Thinking (1 of 3) • Evaluate information and make decision • As simple or elaborate as required • Generally, two ways: – Pre-coded expert knowledge • Typically hand-crafted “if-then” rules + “randomness” to make unpredictable – Search algorithm for best (optimal) solution • Ex- MinMax 23/34 Game Agents – Thinking (2 of 3) • Expert Knowledge – Finite State Machines, decision trees, … (FSM most popular, details next) – Appealing since simple, natural, embodies common sense and knowledge of domain • Ex: See enemy weaker than you? Attack. See enemy stronger? Go get help – Trouble is, often does not scale • Complex situations have many factors • Add more rules, becomes brittle – Still, often quite adequate for many AI tasks • Many agents have quite narrow domain, so doesn’t matter 24/34 Game Agents – Thinking (3 of 3) • Search – Look ahead and see what move to do next • Ex: piece on game board (MinMax), pathfinding (A*) – Works well with known information (ie- can see obstacles, pieces on board) • Machine learning – Evaluate past actions, use for future action – Techniques show promise, but typically too slow 25/34 Game Agents – Acting (1 of 2) • Learning and Remembering – May not be important in many games where agent short-lived (ie- enemy drone) – But if alive for 30+ seconds, can be helpful • ie- player attacks from right, so shield right – Implementation - too avoid too much information, can have fade from memory (by time or by queue that becomes full) 26/34 Game Agents – Acting (2 of 2) • Making agents stupid – Many cases, easy to make agents dominate • Ex: FPS bot always makes head-shot – Dumb down by giving “human” conditions, longer reaction times, make unnecessarily vulnerable, have make mistakes • Agent cheating – Ideally, don’t have unfair advantage (such as more attributes or more knowledge) – But sometimes might “cheat” to make a challenge • Remember, that’s the goal, AI lose in challenging way – Best to let player know 27/34 Game Agents – AI • Deterministic AI – Preplanned, predictable events – Set by rules • • • • Walk forward ten steps then backwards If player is within 5 squares move closer Go to town … take the shortest path using shortest path algorithm Attack player with least health/most damage potential/etc • Non deterministic AI – Unpredictable movement • Random selection of directions – React to environment to learn movement • Player nearby, go slower • Got shot going around corner last time, then take a wider path this time 28/34 CIG • IEEE Symposium on Computational Intelligence and Games – Tutorial – Session Presentation – Competition • http://dces.essex.ac.uk/staff/lucas/cig2008/competitions.html • Competitions Chair: Simon M. Lucas 29/34 CIG Competition 30/34 Unreal Tournament • • • • • • • • Sponsored by 2K Australia The competition task is to create a computer game bot Indistinguishable from a human player major prize of A$7,000 cash Trip to 2K Australia's studio DeathMatch game type for the FPS Chatting will be disabled. Some aspects of the game play will be modified in a way not known to competitors. 31/34 TORCS • • • • • • • Car Racing Daniele Loiacono, Julian Togelius and Pier Luca Lanzi Learn (or otherwise develop) a controller The distance raced in a fixed amount of time Best few controllers will race against each other Mac OS X, Windows and Linux, using Java and C++ Neural networks, Fuzzy logic, Force fields, Expression trees 32/34 Ms Pac-Man • • • • • Non-deterministic game The world record for a human player currently stands at 921,360 Can anyone develop a software agent to beat that? the best software controller for the game of Ms Pac-Man Screen-capture to get the current state of the game 33/34