Artificial Intelligence gaming techniques

Artificial Intelligence Gaming Techniques.Different types of gaming techniques and algorithm are included.SsS*,Dual*,MinMax and Alphabeta Pruning A* and Best first search algorithm .

1. Gaming Techniques in AI Guide: Prof. Dhiraj Jadhav Somnath More(08) Vishwajeet Mote(10) Akanksha Pokale(68) Amit Puranik(79)

2. Content Introduction Why are games relevant to AI The illusion of human behaviour Computer Game types Techniques/Technologies used Game Setup How to play a game by searching Searching techniques Minimax algorithm Alpha-Beta pruning Algorithm SSS* algorithm Applications Game AI major challenges Conclusion

3. Introduction Techniques used in computer and video games to produce the illusion of intelligence behaviour of Non Player Characters(NCP’s). AI has continued to improve with aims set on a player being unable to tell the difference between computer and human players. Approximately 50% game project time is spent on building AI. A Game must ’Feel’ Natural. Obeys law of the game. Character aware of the environment Path finding (A* ,Dijkstra,etc.) Decision making Planning and Time management

4. Why are games relevant to AI AI in gaming is all about enhancing a player's experience. Game playing is considered as an intelligent human activity. Huge state spaces- Games are highly complex, usually there is not enough time to work out the perfect move for example Chess. AI provides different components and its application in majority of video games like racing games ,shooting games or strategy games.

5. The Illusion of Human Behaviour H acks and cheats are acceptable and ,in many cases ,the computer abilities must be toned down to give human players a sense of fairness.E.g. Racing and Shooting AI is on developing rational agents to match or exceed Human performance. AI has aims to player being unable to tell the difference between computer and human players

6. Computer Game Types Strategy Games : Real Time Stratergy Helicopter View Roll Playing Games: Action Games: First Person Shooter(FPS) Spor

7. Techniques/Technologies Used Machine learning Waypoint graph Reinforcement learning Semantic markup

8. Game Setup Two players: A and B A moves first and they take turns until the game is over. Games as search: Initial state Successor function Terminal state Utility function

9. How to Play a Game by Searching General Scheme Consider all legal moves, each of which will lead to some new state of the environment. Evaluate each possible resulting board position Pick the move which leads to the best board position Wait for your opponent’s move then repeat. Key Problems Representing the board Representing legal next boards Evaluating positions Looking ahead

10. Searching Techniques Uninformed Searching(Blind Searching): Breadth First Search(BFS): Depth First Search(DFS): Informed Searching(Heuristic Searching): Best First Search Algorithm & A* Search Algorithm Minimax And Alpha-Beta Pruning

11. Minimax Algorithm BackTracking Algorithm In this algorithm two players play the game, one is called MAX and other is called MIN. Best Move Strategy are Used. Max Will Try To maximize its Utility with best move. Min Will try to minimize its utility with worst move.

12. Properties & Limitations of Minimax Algorithm Complete Optimal Time complexity {O(b^d)} Limitation is the algorithm is slow for complex games such as chess, go,etc.

13. Alpha Beta pruning algorithm( α&β ) There is a technique by which without checking each node of the game tree we can compute correct minimax decision, this technique is called pruning. Pruning technique involves two threshold parameter α and β for future expansion , so it is called alpha-beta pruning. α>=β Key Points about alphabeta Pruning α will try to maximize and β will try to minimize

14. Example: 3 2 7 9 13 Max Max Min β=3 β=2 α=3 α=7 α=2 α=3 α 9 2 1 3

15. Properties : Time Complexity :O(b^(d/2) Optimal It is fast for complex games such as chess, go,etc

16. SSS* Algorithm • St ands for state space search. •It is based on the notion of solution trees. •SSS*' works through two search phases

17. Example

18. Example 12 A

19. Applications Training Simulators Education Entertainment Virtual Environment Movies

20. Game AI major challenges Resources Deadlines Over Intelligence Human Level Intelligence

21. Conclusion Techniques used in video games. Importance of AI Computer game types Techniques Used for creating these AI bots Searching techniques Minmax Algorithm Alpha Beta pruning algorithm( α&β ) SSS* Algorithm

22. Thank You!