Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

If you were going to write a chess game engine, what programming paradigm would you use (OOP, procedural, etc) and why whould you choose it ? By chess engine, I mean the portion of a program that evaluates the current board and decides the computer's next move.

I'm asking because I thought it might be fun to write a chess engine. Then it occured to me that I could use it as a project for learning functional programming. Then it occured to me that some problems aren't well suited to the functional paradigm. Then it occured to me that this might be good discussion fodder.

share|improve this question
1  
This is akin to writing a C compiler from scratch. I would not reinvent the wheel. I would study the existing ones first. –  Job Jan 8 '11 at 16:37
9  
@Job: My goal is the process rather than the result. Even if I end up with a very bad engine, I think there could be value in the process of analyzing the problem and developing a way to attack it, especially if I learned some new programming methods in the process. –  poke Jan 8 '11 at 16:50
1  
Good luck. No real employer will ever ask you to develop one from scratch, but during an interview they might ask how you would attack the problem. –  Job Jan 8 '11 at 16:54
5  
@Job a large portion of embracing the programming life is coding things not because there's a definite need for them, but because you can. –  user8 Jan 8 '11 at 22:14
1  
@Mark, how about embracing life ;) = travel, languages, theater, poetry, outdoors, etc.? I like programming, but when I am not doing it per se, I have 1000 other things to do. –  Job Jan 8 '11 at 23:15
show 3 more comments

5 Answers

up vote 8 down vote accepted

Evaluation isn't a parallelizable problem as far as I know but evaluating different chains is , so I definitively would write it to make use of multiple cores and multithreading.

Whether you go functional or semi-functional is a matter of taste. Personally i'd go OOP and use the support for functional programming and parallelization that exists in for instance C#

On a sidenote, if I were to write a chess engine I'd try to make one that really can "think" about chess. Using board evaluation to brute force all possible combinations has been done to death and extremely well, but there hasn't been much progress afaik in doing a more thinking/fuzzy chess engine. That'd be a challenge! :)

Find some games with really tricky position play and strong moves (they're marked ! or !!) and use them to train and test your engine.

share|improve this answer
    
+1 for going semi-functional –  Anonymous Type Nov 30 '11 at 3:26
add comment

Have a look at how Dan and Kathe Spracken used to do it back in the days where 64 Kb RAM was a luxury: http://archive.computerhistory.org/projects/chess/related_materials/oral-history/spacklen.oral_history.2005.102630821/spracklen.oral_history_transcript.2005.102630821.pdf

I believe that would be a really good place to start for learning the basics.

share|improve this answer
add comment

I guess it depends upon your goals, which I take are strictly didactic. If you were trying to write a competitive product, you would want maximum efficiency in the lowest level evaluators. Lots of opportunity for bit level parallelism here. Also lots of opportunities for hash tables. Also opportunities to exploit parallelism. Then at the higher levels, you probably want a system good for AI, so that probably means a functional programming languauge. Obviously you don't want to do all of these things, pick one or two of them, and be content with the fact that your project will not be competitive with the better programs.

share|improve this answer
add comment

I have choosen OOP paradigm in my chess engine named The Turk. First version of my chess engine was written more procedural rather than OOP.Then i found so hard to improve my chess engine because of long code blocks and poor design.

It depends on what you want to achieve while writing chess engine.If you want to create a chess engine which is too strong so it even not possible to do this in OOP languages because of slow late bindings. If you just want to learn programming and also get fun by writing chess engine so managed languages and OOP will be your friend. I can suggest you to choose C# because it is also possible to write chess engine in more procedural way with it.

share|improve this answer
    
How does it rate ELO-wise? Compared to Crafty? –  user1249 Jan 9 '11 at 12:36
    
@Thorbjørn Ravn Andersen - Crafty one of the superior open source chess engine written in C and by Dr. Robert M. Hyatt who has been spend his life in chess programming. Unfortunality i haven't tested elo rating because still there are many things to do before test elo rating.Currently evaluating is just evaluate piece values so it has quite weak evaluation and still i haven't implemented all necessary algorithms yet. Unfortunality i have no time to spend on this project at the moment. I hope that one day will be possible to continue on it. –  Freshblood Jan 9 '11 at 15:14
    
ah sorry, I thought it could actually play. My bad. –  user1249 Jan 9 '11 at 18:57
    
@ Thorbjørn Ravn Andersen - I have published some releases there and latest repository changeset ready to build. I just wanted to say it is quite weak at the moment. –  Freshblood Jan 11 '11 at 12:49
add comment

I ported a simple chess program as a means of learning the Forth language. It turned out to be a great fit to this very imperative problem, and I learned a lot. The open stack allowed me to implement alpha-beta search in a unique fashion which gave me greater insight into the algorithm.

One would think that functional programming would be great for chess programs, since the core algorithms (alpha-beta depth-first search, evaluation) are recursive and functionally strict. However, a chess program lives and dies on efficiency and none of the current crop of functional languages have that aim. The top one hundred state-of-the-art engines all use imperative languages (mostly C/C++, then Delphi) in order to have maximum control over memory usage, multi-threading, global state, and code generation. All functional languages use dynamic memory allocation for core data structures, which is death for a chess program.

I'd still like to see someone make an attempt to break into the top 100 chess engines using a functional language.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.