How to Start Your First Computer Chess Program

Under Construction: lots of work to do here

We are in the process of creating two equally strength very very beginner programs. The programs will not have much in them but they will play a legal match and interface with winboard. One program will be based on simplistic data structures and written in C. The other will be based on bitboards and written in C++.

It is preferable that you write your own chess program from scratch. However, this can be a daunting effort. So, we are accepting clones of the very weak program versions mentioned here. You can clone one and make your own modifications. Don't copy others code and put it into these. The idea is that one can start with this method and learn much. After some experience, one moves own to completely writing their own program. Thus, this is meant to facilitate a neophyte in rapidly learning the fundamentals.

We thank James Swafford for providing the alpha version of his program Prophet for this.

• James' web page
• James' Download Page -- Only the Alpha version, at the bottom of the page, is allowed in the ACCA tournaments unless you completely write your own from scratch.

Current Steps:
• Take at least two programming classes and a data structures class
  • Learn C or C++ before starting this.
  • Learn to compile and build multi file programs.
  • Learn to use a debugger. There might be times when the one in your head is overtaxed by a problem.
  • Taking an algorithms class and an AI class would be a good idea.
  • Read a book on computer chess programming.
  • After reading the book, review some of the recommended instructional websites.
  • A little theory: Would a chess program developer toss some NPS when improving the search and why?
• The Gui:
  • Understand the Winboard Protocol: read the design document.
  • Ask questions on the various forums.
  • Create a very simple small program that barely interfaces with Winboard? It should simply receive moves and interactively send 4 preprogrammed moves to Winboard to be made on the screen.
• The Chess Program:
  • Pick one of the two beginner programs as your base.
• Create a design document for the program (You will need this again and again)
  • Look over the code. Which platform is it designed for? Unix, Microsoft, MAC or is it portable?
  • Review every line of it and understand how it works as a whole. Create a flow diagram or state chart.
    • The flow diagram should document the different procedures/functions and the flow between them (not every detail of every function).
  • Understand and know the data structures and/or classes.
  • Understand and know how the different parts work together and communicate with each other.
    • How does the interface to Winboard work? Know each command.
    • Does the program support interrupting the search from Winboard? What are the implications to that?
    • How does the legal move generator work? How is the data collected and used in making a move?
    • Which Winboard commands are unsupported? Does Analyze mode work? How about force and go or move now?
    • Does the program support a opening book?
    • Does the program have a benchmarking mechanism? Yes, how do you run it?
    • Does it support loading position files or whole games?
    • Are there any debugging features built into the program? A trace facility for the search?
  • What is in the position evaluator (PE)? Write down what it considers and its bonuses and penalties in chess terms not programming terms.
  • If you don't know much about chess position evaluation, read a good book on chess strategy or position analysis.
  • What techniques are used in the search procedures? Any extensions, reductions or pruning?
• What is missing from the program?
  • Create a list of what can be improved or is missing before coding. (This is where the chess programming book and instructional web pages come in. You did do that didn't you?)
• Create a journal of your work.
  • Run the benchmarks and document the speed and node counts for each of several forced ply searches.
  • Run a gauntlet with several opponents at blitz time controls. Record the results in your journal.
  • Also, record your thoughts on the draws and losses as to why they were so. Was your program out searched?
• Get your feet wet on the less tricky stuff first:
  • Move Ordering
    • Improve the move ordering. There are many ways to achieve this. Use your own thoughts first.
    • Rerun the benchmarks, document and compare the results. Did it work? No, try again.
    • You made it faster!! Now, rerun and record the results in your journal.
  • Search Algorithm Improvements:
    • The programs only have minimax/negamax. Implement alpha/beta pruning. That should produce a 6x speed up in time to ply.
    • Test to see that you implemented it properly.
    • Run and record the benchmark results.
    • Run the gauntlet again with the same opponents (make sure your opponents don't have any kind of learning) and record the results.
    • Did it perform better? Do you need weaker sparring partners?
  • Simple improvements to the PE.
    • Bonus for the two bishops.
    • Penalty for doubled pawns.
    • Bonus for rooks on the 7th rank.
• The tricky stuff:
  • Advanced Move Ordering techniques (Killer Moves, History Heuristic)
  • Null Move Pruning
  • Reductions
  • Extensions
  • PV Search
  • Aspiration Windows
  • Pawn Hash
  • Transposition Tables
  • Improvements to the P.E. (That book you read on human chess strategy or pawn structure)
  • Lazy Evaluation
  • Improve the Quiescence search
  • King Safety
• The very tricky stuff:
  • Thread or multiprocess your program. If you don't know the difference, then don't try either of them.
• Maybe join the ICGA (International Computer Games Association) and read the quarterly journals
  • Look over the online table of contents from past issues. Purchase the ones interesting to you (if you can't find a reprint on the web).

Copyright Charles Roberson