Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

writing logic for chess game

 
Ranch Hand
Posts: 116
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If one wanted to approach writing a chess game what would be the considerations .

Most rudimentary ( and probably impossible approach )
To take a stab ::

First move by white consists of following possibilities ::
16 Pawn moves
4 Knight moves ( 2 possible moves for each Knight)

So total possibilities = 20 for the first move by white

Now for each move the possibilities grow exponentially .

Obviously this is not the way to go .
Also rather than just brute force - there is also the need to make the best possible move

Just curious - how are such programs written ?

what is the approach used ?

how is the inteligence of choosing the best move written ?

Thanks ,
~satish
[ October 09, 2008: Message edited by: satish bodas ]
 
author
Posts: 9000
19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is a huge topic, but some common ideas are:

1 - You create a method that looks at any given position and makes an evaluation about how "good" or "bad" that position is. This method is often called a "static evaluation function" (SEF),because it looks only at a static position.

2 - You create a "Search tree" much as you discussed. In your example the beginning position would be the base or "root" of the tree, and you would have 20 white moves branching off of the root. For each of those 20 branches you would have 20 black branches, for each of those ~20-40 white branches, then black, then white, and so on. (Each set of branches is called a "ply".) Because computers are not infinitely fast and do not have infinite memory, you have to choose an arbitrary maximum number of plies to create and evaluate.

3 - You apply your static evaluation function to each of the positions you created and you assign each spot or "node" on the tree a value.

4 - There are various "minimum - maximum" algorithms that you can use to review the search tree's values and pick the best possible next move.

There are various ways to limit the size of the tree as you build it (called "pruning"), and of course creating a good SEF is a very difficult task. Typically your SEF would consider things like how many pieces each player has, how much each player controls the center of the board, how many total moves each player can make, how safe is each king, and so on.

This overall approach can be used for Chess, Checkers, Go, Backgammon, Othello, Connect-4, Pente, Go-Moku, and on and on.

hth,

Bert
 
satish bodas
Ranch Hand
Posts: 116
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks a bunch Bert for giving an insight

I dont know how much I can achieve - but will start giving it a thought and then some shot !



Thanks ,
~satish
 
Consider Paul's rocket mass heater.
    Bookmark Topic Watch Topic
  • New Topic