I want to write a Chess program

[VinylxScratches]

I'm trying to find a focus application. I honestly don't know what to program and doing these little exercises do not feel rewarding.

I have at my disposal a Macbook with Xcode. Maybe I can program for the iPhone? I also will be building a Windows XP machine soon and I have Visual Studio 2008 from college.

My experience with programming is mostly with C#/VB.NET/ASP.NET and C++.

 

[ObscureCaucasian]

Well you're .NET languages obviously aren't as well supported on the Mac platform, and iPhone uses Objective-C which I believe is a superset of C. It deviates from C syntax wise, but I've heard it's not too hard to pick up. XNA Game Studio is available for Visual C# 2008 Express and is essentially the current implementation of Managed Direct X. Games run on Windows/Xbox 360/Zune, and is pretty easy to pick up (as far as graphic programming goes). It's up to you as to what environment makes you the most comfortable and has the best target platform.

 

[Markbnj]

Feeling ambitious? . Chess is a deep search problem. Really not very complicated, and almost completely a matter of horsepower, which is why you find the best machine chess programs running on hairy Blue Gene-type machines from IBM that operate in petaflop territory. If you want to run the same program on Windows XP it's just a time tradeoff: make your move and then take a three-year vacation while the machine searches.

Any of the languages you mention will be fine for what you want to do, but given the cycles you have available none of them will be able to do a very good job of playing chess in a reasonable amount of time, but if it's a particular interest of yours then go for it.

 

[DaveSimmons]

You should be able to find endless material on how to optimize the search for moves, it's been a part of AI research for several decades.

Also google "gnu chess" for open-source code you could port to the iPhone if it hasn't been done already. for .net you might port it to Silverlight and WPF.

 

[degibson]

FWIW, subsets of chess have been shown to be NP-complete, so it follows that chess itself has no known optimal algorithm. In other words, you will have a lot of latitude to come up with chess heuristics.

Don't worry too much about the computational complexity -- Markbnj is correct that the 'best' chess programs, like Deep Blue, run on supercomputers, but your chess program doesn't have to beat Gary Kasparov. There are free (e.g. gnuchess) and commercial (e.g. Chessmaster) chess applications that are very challenging for nearly all users and compute moves in seconds on contemporary hardware.

I don't mean to underestimate its complexity. It is NP-complete. Use a high-performance language for your AI computations. It won't matter at all what you use for the UI layers.

If you try to make an iPhone app, keep your heuristics really simple. There will be a big performance gap between iPhone and desktop, of course.

 

[DaveSimmons]

^ it's definitely possible. Atari had a decent chess program for the 800 back in 1978 (1.79 MHz 6502 CPU) and games like Battle Chess and Chessmaster ran well on 8 MHz 80286 PCs.

 

[Cogman]

The problem you might run into is that you as a programmer will be tempted to "solve" the chess problem. As others have stated, that isn't possible as you basically have to calculate the consequences for every move possible to get to the best solution.

Instead, think of using something like a points based system and a shallow search (Calculate 3 moves deep for example.) Then Assign point values to each piece, EG, pawns are 1 pt, bishops 2, knights 3, ect. And move pieces according most points gained (by taking a piece) and least points lost. That should give a fairly good chess program.

 

[Markbnj]

Originally posted by: DaveSimmons
^ it's definitely possible. Atari had a decent chess program for the 800 back in 1978 (1.79 MHz 6502 CPU) and games like Battle Chess and Chessmaster ran well on 8 MHz 80286 PCs.

I'm not a chess expert, and in fact don't play often or well, but I did a ton of research on the subject back in the early 90's when I was writing a neural net-driven backgammon program (a much harder problem domain than chess, imo). Popular chess programs that run or ran on Windows, Mac, etc., were/are able to challenge decent players. I'm characterizing here, because I don't recall the actual numbers, but let's say that a decent player is able to see 2-3 moves ahead on the board. By comparison a grand master can foresee 5-8 moves forward, or further. That's why you need supercomputer bandwidth to beat a grand master. The curve falls off pretty steeply, and I don't think Battlechess or any PC-based program like that will pose much challenge to a "good" player. Those programs cannot search more than 2-4 moves forward in reasonable time. Since they can't, they employ evaluation shortcuts, which I'm no longer equipped to discuss in detail, but which probably include ideas like those Cogman mentioned.

So you can optimize the search algorithms, data structures, reduce the subset of the tree that needs to be searched, etc., but it basically comes down to how fast you can build and search positions.

Backgammon, as a side note, has several orders of magnitude more possible positions than chess due to the randomizing factor of the die at each turn. We could never make searching work for backgammon. Heuristics worked but could only win at the beginner level. We turned to a neural network that was built and trained at USC and CMU by Justin Boyan and Marc Ringuette. It was pretty decent, but programs like TD-Gammon soon beat us using approaches based on genetic algorithms.

 

[DaveSimmons]

Yes, the Atari Chess or Battlechess can beat lazy amateurs like me but wouldn't challenge someone who plays less haphazardly. To me, playing chess well is too much like what I do all day for work in development

For fun I'd rather relax in the wastelands of Fallout 3 or deal with illegal aliens in X-Com.

 

[Markbnj]

Originally posted by: DaveSimmons
Yes, the Atari Chess or Battlechess can beat lazy amateurs like me but wouldn't challenge someone who plays less haphazardly. To me, playing chess well is too much like what I do all day for work in development

For fun I'd rather relax in the wastelands of Fallout 3 or deal with illegal aliens in X-Com.

I'm even lower than the lazy amateur category . I'm probably in the "knows the movement rules" category.

 

[Apathetic]

In chess, pieces are generally worth the following amounts:

Pawn: 1 point
Knight: 3 points
Bishop: 3 points
Rook: 5 points
Queen: 9 points

I recommend pulling down the source for GnuChess and taking a look at their code to give you some ideas.

Good luck!

Dave

Edit: damn typo

 

[TheLonelyPhoenix]

I did something like this for Othello back when I was a wee lad taking Data Structures.

To do a basic 'brute-force' AI, you use a recursive function to cycle through all the possible moves up to your desired "depth" (number of moves ahead you want your AI to look), then have your base-case evaluate the position - for chess, the most basic board evaluation is simply a point-count of your pieces compared to the opponents, and a checkmate is "infinite" points. That number is used to evaluate which branch you should take as you move back through the recursive returns - the AI chooses the branch which leads to the most points for it, and assumes its opponent will choose the branch that leads to the least points for the AI. After you get that far, you can play with more complex board evaluations (pawn structures, piece development, etc) and such, then take it from there.

If you haven't learned about recursive algorithms yet, start your learning there and just program a tic-tac-toe game for practice. A computer can calculate all possible tic-tac-toe games quite easily (so you don't have to worry about depth and board evaluation) so it would be the best place to start.

Good luck.

 

[KIAman]

I wrote a chess program in my AI class which had a specific CPU speed (1.2 ghz CPU) and only had 10 seconds to make a move. The first part only spit out piece name and coordinates so that our programs could play each other's programs. Later on, we added the graphical board, to make it more fun.

Anyways, everyone used the standard n-depth recursive search and with only 10 seconds to move, most could only afford to go 4 layers, some inefficient coders could only go 3 layers.

I ended up using a combination of n-depth search and a large hash table (no requirement on space) which had about 100 different patterns and their associated moves (about the first 10 moves). My program only searched 3 layers but having the pattern table in combination with brute strength allowed me to win against everyone else.

How did I get 100 patterns for the first 10 moves? I borrowed a real chess program and made it play itself couple hundred times and saved the results.

Now, try writing a checkers program... that will blow your mind. It's about 100 times more complicated than writing a chess program.

 

[Markbnj]

I ended up using a combination of n-depth search and a large hash table (no requirement on space) which had about 100 different patterns and their associated moves (about the first 10 moves). My program only searched 3 layers but having the pattern table in combination with brute strength allowed me to win against everyone else.

Very cool. I was thinking about something like this last night when reading through this thread.

 

[Ken g6]

That table with the first few moves is called an "opening book". Most of the big chess programs have opening books, and also closing books, which hold boards with just a few pieces and have standard strategies to win. Closing books more or less consist of the solutions to "chess puzzles" that you may see occasionally.

 

[Cogman]

Originally posted by: KIAman
I wrote a chess program in my AI class which had a specific CPU speed (1.2 ghz CPU) and only had 10 seconds to make a move. The first part only spit out piece name and coordinates so that our programs could play each other's programs. Later on, we added the graphical board, to make it more fun.

Anyways, everyone used the standard n-depth recursive search and with only 10 seconds to move, most could only afford to go 4 layers, some inefficient coders could only go 3 layers.

I ended up using a combination of n-depth search and a large hash table (no requirement on space) which had about 100 different patterns and their associated moves (about the first 10 moves). My program only searched 3 layers but having the pattern table in combination with brute strength allowed me to win against everyone else.

How did I get 100 patterns for the first 10 moves? I borrowed a real chess program and made it play itself couple hundred times and saved the results.

Now, try writing a checkers program... that will blow your mind. It's about 100 times more complicated than writing a chess program.

Checkers is a solved game though Just download the database of moves, look for the current board position, and make the move that will result in you winning

 

[zebano]

Well this can be split into two parts. The engine, and the GUI. If it's the engine you're interested in, look up UCI engine. There are lots of GUIs you can plug this into and play against it (i.e. WinBoard, ChessBase etc.) and you can enjoy the difficult problem of optimizing your search.

 

[Argo]

The biggest challenge with chess is evaluation function. How do you evaluate one position against the other. One possibility is to use piece values provided earlier in this tread and then adding them up. I guarantee that any program that does that will get bitten into a pulp by any amateur.

A better program will use deeper analysis: number of opponents pieces you're attacking, number of your pieces under attack, number of "key" squares under your and opponents attacks, freedom of movement by various pieces. That's where a lot of power of modern chess algorithms lie.

Btw, they are trying to solve chess completely from the end by creating all possible N piece combinations and DEEP solving them. They're up to 7 piece positions now and came up with such interesting positions as "white wins in 1500 moves", positions that were previously considered a draw.

 

[oog]

Originally posted by: DaveSimmons
You should be able to find endless material on how to optimize the search for moves, it's been a part of AI research for several decades.

Also google "gnu chess" for open-source code you could port to the iPhone if it hasn't been done already. for .net you might port it to Silverlight and WPF.

one nice thing about gnuchess is that they separate the underlying engine from the board that interacts with it. you could decide to port either part of it.

 

[CrazyLazy]

Originally posted by: Argo
Btw, they are trying to solve chess completely from the end by creating all possible N piece combinations and DEEP solving them. They're up to 7 piece positions now and came up with such interesting positions as "white wins in 1500 moves", positions that were previously considered a draw.

Normal checkers, I believe, has already been solved in this manner. The flying kings version is still unsolved, but it's something that's in reach within a few years. I think it will be interesting to see if once Chess is solved humans will simply stop playing the game. It's still a form of entertainment I suppose but for me knowing that the game has been totally played through kind of rains on my parade.

 

[degibson]

Originally posted by: CrazyLazy

Originally posted by: Argo
Btw, they are trying to solve chess completely from the end by creating all possible N piece combinations and DEEP solving them. They're up to 7 piece positions now and came up with such interesting positions as "white wins in 1500 moves", positions that were previously considered a draw.

Normal checkers, I believe, has already been solved in this manner. The flying kings version is still unsolved, but it's something that's in reach within a few years. I think it will be interesting to see if once Chess is solved humans will simply stop playing the game. It's still a form of entertainment I suppose but for me knowing that the game has been totally played through kind of rains on my parade.

One interesting variant on this idea is whether the game can be solved or not. I think its easier to prove that there exists a solution to, say, checkers, than it is to actually solve it. I have no idea if the same holds for chess (proofs were never my strong point). Even so, I'm sure chess will remain very popular -- after all, people have been playing chess for 700 years now.