Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

checkers

mini project
by

Varun Khaitan

on 14 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of checkers

Varun Khaitan
Nimit Acharya Developing the Game of Checkers
with User Assistance System Software Engineering Model Iterative and Incremental Development Model Introduction Our base paper: Rules of the game Starting position – Each player starts with twelve pieces on the dark spaces of the three rows closest to that person's own side
A simple move involves sliding a piece one space diagonally forwards to an adjacent unoccupied dark square.
Regular capture is when you jump over a diagonally adjacent piece into and empty square.Regular capture is possible only in forward direction, except if the capture is a part of multiple stages capture on the same move, it's possible to capture also backward.
When a pawn reaches the last line it is crowned to King. Kings are able to move both backward and forward and they're also able to capture both backward and forward.
A player wins by capturing all of the opposing player's pieces or by leaving the opposing player with no legal moves.
Minimax:The Algorithm It is a decision rule used in decision theory, game theory, statistics and philosophy for MINImizing the possible loss while MAXimizing the potential gain.
A search tree is generated, depth-first.Then, the final game position is evaluated from MAX’s point of view. Afterwards , the inner node values of the tree are filled bottom-up with the evaluated values. The nodes that belong to the MAX player receive the maximum value of its children. The nodes for the MIN player will select the minimum value of its children.
So the MAX player will try to select the move with highest value in the end. But the MIN player will try to select the moves that are better to him, thus minimizing MAX’s outcome.
About the Application The Application is made to implement a game of checkers.
AI uses minimax algorithm with heuristic function 1.
User assistance system uses minimax algorithm with alpha beta pruning with heuristic function 2.
User can make a move using the GUI provided.
The chat option is used for AI to give hints and tips to the user to improve his skill set and help him through the game. Alpha Beta Pruning Minimax algorithm can be inefficient and may use further optimization.
Sometimes the search can be aborted because we find out that the search subtree won’t lead us to any viable answer.
1.Have two values passed around the tree nodes:
Alpha(max) and Beta (min)
2.At MAX level, before evaluating each child path, compare the returned value with of the previous path with the beta value. If the value is greater than it abort the search for the current node;
3.At MIN level, before evaluating each child path, compare the returned value with of the previous path with the alpha value. If the value is lesser than it abort the search for the current node.
Possible Improvements Using ordering heuristics to search parts of the tree that are likely to force alpha-beta cutoffs early.
Changing heuristic function for end game as the paradigm changes drastically.
Allowing user to ask queries to the AI for a better gaming experience.
Using a dynamic programming cache so same moves donot calculate score redundantly Heuristic Functions Used Function 1:For opponent AI Implementation Issues Class Diagram
Conclusions This project helped in ascertaining certain facts.
The following are few of them:
•Heuristics can be drastically improved by adding specific features.
•The depth of the game tree has significant influence on the quality of the computer player.
•There's a tradeoff between calculation time and quality of game.
•Alpha-Beta pruning is exponentially improving in comparison to Minimax as the depth grows.
User learns much quicker and performs better with the Assistance system.
Combination of both iterative design or iterative method and incremental build model for development.
The basic idea behind the agile method is to develop a system through repeated cycles (iterative) and in smaller portions at a time (incremental).
The unified process groups increments/iterations into phases: inception, elaboration, construction, and transition.
We chose this because this model makes coding complex projects easier and is widely used when GUI and error prone coding is involved.
An Artificial Intelligence system to help the player of Real-Time Strategy games Our aim is to develop an AI to help the user play against the opponent and develop his skills.Even new players can learn the game without much effort and the transition from a novice to a professional is smooth and fast.Our approach is to create a computer agent based on the Minimax algorithm for the AI, together with possible improvements, which is the state of the art in one-on-one games.
We chose the game of checkers as it is a very popular yet complex game for which AI help can drastically improve your skill. Function 2:For User Assistance System Score=(No. of Opponent Pieces)/(No. of Own Pieces) Score=(Sum for Opponent)/(Own Sum)
where Sum = 2*(no. of kings)+(no. of other pieces)
Use Case Diagram We chose to implement the board as an integer array of 36.
all single moves are done in increments of +/-4 and +/-5
jumps are done in increments of +/-8 +/-10
The board was made using images for each cell to give a rich user experience.
Hint highlighting was done to make it easier for user to understand tips.
Full transcript