Connect with us

PC Drafts

How to create chess game in java

How to create chess game in java

History of Chess game:

  • 1950: Programming a Computer for Playing Chess (Claude Shannon)chess game
  • 1951: First chess playing program (on paper) (Alan Turing)
  • 1958: First computer program that can play a complete chess game
  • 1981: Cray Blitz wins a tournament in Mississippi and achieves master rating
  • 1989: Deep Thought loses 0-2 against World Champion Garry Kasparov
  • 1996: Deep Blue wins a game against Kasparov, but loses match 2-4
  • 1997: Upgraded Dee Blue wins 3.5-2.5 against Kasparov
  • 2005: Hydra destroys GM Michael Adams 5.5-0.5
  • 2006: World Champion Vladimir Kramnik looses 2-4 against Deep Fritz (PC
    chess engine)

Complexity of a Chess game:

  • 20 possible start moves, 20 possible replies, etc.
  • 400 possible positions after 2 ply (half moves).
  • 197 281 positions after 4 ply.
  • 713 positions after 10 ply (5 White moves and 5 Black moves).
  • Exponential explosion!
  • Approximately 40 legal moves in a typical position.
  • There exists about 10120 possible chess games .

Search Trees and Position Evaluation:

  • Search trees (nodes are positions, edges are legal chess moves).
  • Leaf nodes are end positions which needs to be evaluated (judged).
  • A simple judger: Check mate? If not, count material.
  • Nodes are marked with a numeric evaluation value.

chess game

The Basic Search Algorithm:

Minimax: Assume that both White and Black plays the best
moves. We maximizes White’s score
Perform a depth-first search and evaluate the leaf nodes
Choose child node with highest value if it is White to move
Choose child node with lowest value if it is Black to move
Branching factor is 40 in a typical chess position
White
Black
White
Black     

white

chess game
ply = 0
ply = 1
ply = 2
ply = 3
ply = 4

 

Pruning Techniques:

  • The complexity of searching d ply ahead is O(b*b*…*b) = O(bd)
  • With a branching factor (b) of 40 it is crucial to be able to prune the search tree .

Analyze the Best Move First:

  • Even with alpha-beta pruning, if we always start with the worst move, we still get O(b*b*..*b) = O(bd).
  • If we always start with the best move (also recursive) it can be shown that complexity is O(b*1*b*1*b*1…) = O(bd/2) = O(√bd).
  • We can double the search depth without using more resources.
  • Conclusion: It is very important to try to start with the strongest moves first .

Killer-Move Heuristics:

  • Killer-move heuristics is based on the assumption that a strong move which gave a large pruning of a sub tree, might also be a strong move in other nodes in the search tree.
  • Therefore we start with the killer moves in order to maximize search tree pruning.

Zero-Move Heuristics:

  • Alpha-Beta cutoff: “The position is so good for White (or Black) that the opponent with best play will avoid the variation resulting in that position”.
  • Zero-Move heuristics is based on the fact that in most positions it is an advantage to be the first player to move.
  • Let the player (e.g. White) who has just made a move, play another move (two moves in a row), and perform a shallower (2-3 ply less) and therefore cheaper search from that position.
  • If the shallower search gives a cutoff value (e.g. bad score for White), it means that most likely the search tree can be pruned at this position without performing a deeper search, since two moves in a row did not help.
  • Very effective pruning technique!
  •  Cavecats: Check and endgames (where a player can be in “trekktvang” – every move worsens the position) .

Transposition Table:

  • Same position will commonly occur from different move orders.
  • All chess engines therefore has a transposition table (position cache).
  • Implemented using a hash table with chess position as key.
  • Doesn’t have to evaluate large sub trees over and over again.
  • Chess engines typically uses half of available memory to hash table – proves how important it is.

Download chess game code in java:

 

Continue Reading
You may also like...

Abdur Rehman (Born July 7, 1993) is a student of Software Engineering and a founder of pcdrafts.com. I am a graphic designer, blogger, geek and a man behind the pcdrafts.com. I am currently living in Peshawar, Pakistan. With integrated time along with my study, I have been working on the different computer project. Recently I am working with the organization named E-MO. I love to learn and experience new stuff and put them to the test. I love spending time on the computer and reading books and so on.

Click to comment

Leave a Reply

Your email address will not be published. Required fields are marked *

More in Programming

Like Us OnFacebook

Popular Posts

To Top