Help Needed for Chess Programming

[Anonymous]

Hi Friends,

I need some help from you all chesslovers and chess programmers. I am doing my final year Btech project on developing a computer program that can play (standard) chess successfully. As most of you are playing chess for a long time, and I assume that you have good knowledge of chess (and are good chess programmers also), can you please help and tell me about some useful resources on the internet related to 'chess programming' or any useful sites, articles or books related to chess programs, that can give me some ideas on what are the user needs and how to successfully write a chess program?

Also where I can find the source code for various chess engines? I also like to know in which language should I program? Any suggestions.

I also need some help for the interface part. Do you know anything about it? And can you suggest me where to look for some standard interfaces for playing chess? I look forward to a helpful response, and thanks for any help that you can provide.

Any help and suggestions you provide will be greatly appreciated.

Thanks in advance.

best regards,
abhay
DA-IICT, Btech, 4th yr
INDIA

PS: You can also mail your replies to: abhay_kumar at da-iict.org
abhay.kumars at gmail.com

[Pradu]

Hi Friends,

I need some help from you all chesslovers and chess programmers. I am doing my final year Btech project on developing a computer program that can play (standard) chess successfully. As most of you are playing chess for a long time, and I assume that you have good knowledge of chess (and are good chess programmers also), can you please help and tell me about some useful resources on the internet related to 'chess programming' or any useful sites, articles or books related to chess programs, that can give me some ideas on what are the user needs and how to successfully write a chess program?

If you just want a simple chess program, all you have to do is implement a board structure and the ability to do makemove with an alphabeta algorithm.

You can find some helpful links here : http://witz.sf.net/links.php.

Also where I can find the source code for various chess engines? I also like to know in which language should I program? Any suggestions.

Search google for TSCP. It will help you get your protocol problems sorted out. TSCP does not implement the Winboard protocol as it should bit it is good enough.

I also need some help for the interface part. Do you know anything about it? And can you suggest me where to look for some standard interfaces for playing chess? I look forward to a helpful response, and thanks for any help that you can provide.

Any help and suggestions you provide will be greatly appreciated.

Look at TSCP's xboard() and look at the Winboard Protocol.
http://www.tim-mann.org/xboard/engine-intf.html

Thanks in advance.

best regards,
abhay
DA-IICT, Btech, 4th yr
INDIA

PS: You can also mail your replies to: abhay_kumar at da-iict.org
abhay.kumars at gmail.com

I suggest you write your program in C, but it is just my preference.

[Dann Corbit]

Hi Friends,

I need some help from you all chesslovers and chess programmers. I am doing my final year Btech project on developing a computer program that can play (standard) chess successfully. As most of you are playing chess for a long time, and I assume that you have good knowledge of chess (and are good chess programmers also), can you please help and tell me about some useful resources on the internet related to 'chess programming' or any useful sites, articles or books related to chess programs, that can give me some ideas on what are the user needs and how to successfully write a chess program?

Probably, most people in this particular forum are better programmers than chess players, but there are a few real chess experts too (like Vincent and Uri).
To write a chess program, you will need to decide on a board structure. The most popular formats are 0x88 and bitboard. I think 0x88 will be quicker to understand but if you are already a good programmer and if you like bit twiddling, then bitboard might be more fun for you (I like it better).

I recommend these articles first:
http://www.seanet.com/~brucemo/topics/topics.htm
http://www.frayn.net/beowulf/theory.html

Then read each of this series of articles:
http://www.gamedev.net/reference/progra ... es/chess1/

Now, you are ready to read this:
http://members.home.nl/matador/chess840.htm

There is lots of stuff here:
http://wbec-ridderkerk.nl/html/ProgrLinks.html

Also where I can find the source code for various chess engines?

Go here:
http://wbec-ridderkerk.nl/
Click on the "Engine Info" menu option. The programs with source code have an entry that tells you.

I also like to know in which language should I program? Any suggestions.

C or C++ if you know either of those two languages.
Next best would be Delphi, or a .NET language
I would recommend against assembly.

I also need some help for the interface part. Do you know anything about it? And can you suggest me where to look for some standard interfaces for playing chess? I look forward to a helpful response, and thanks for any help that you can provide.

You have two basic choices. There is Winboard interface, and there is UCI interface. They are about the same difficulty. This is actually harder than it might seem at first, because of the character based interface. One of the most important details is to make very sure that you have all input and output buffering TURNED OFF. Otherwise, your program will play very unpredictably.
Read this site:
http://www.aarontay.per.sg/Winboard/index.html
especially for the interface, consider:
http://www.aarontay.per.sg/Winboard/Winboard1.html#[A.14]

Any help and suggestions you provide will be greatly appreciated.

Thanks in advance.

best regards,
abhay
DA-IICT, Btech, 4th yr
INDIA

PS: You can also mail your replies to: abhay_kumar at da-iict.org
abhay.kumars at gmail.com

[Anonymous]

Hi,

Thanks for all the replies. I wasn't expecting such great help in such a short time!

I checked the links and found them to be quite useful, especially the gamedev.net link.

I would like to know If it's possible that if I write in Java, then I would be able to implement the winboard protocol.

Any good books you know for programming that you want to recommend? And how tougher is to build your own interface?

I look forward to some more help.

Thanks again,
Abhay Kumar

[Dann Corbit]

Hi,

Thanks for all the replies. I wasn't expecting such great help in such a short time!

I checked the links and found them to be quite useful, especially the gamedev.net link.

I would like to know If it's possible that if I write in Java, then I would be able to implement the winboard protocol.

Yes. The gemdev.net link is a Winboard engine written in Java. There are several Java chess engines with source code round about. None of them are very strong. I think that there are one or two private engines that are quite strong, and (If I recall correctly) Spike [an extremely strong engine] is written in a subset of Java and C++ that is compatible to both languages so that they can develop in Java and then have peak performance.

Any good books you know for programming that you want to recommend?

Programming in General:
Anything by Sedgewick or Knuth. Also Weiss and Budd are good.
If you want language specific books, I would need to know what language.
For chess programming books, the only one that I have is this one:
http://supertech.lcs.mit.edu/~heinz/node1.html

And how tougher is to build your own interface?

It isn't trivial, but you do not have to do something real advanced right away. If you are deciding on which interface to use (Winboard or UCI) then UCI makes it much easier to configure an engine, and Winboard is the simpler interface for game play. But all in all, they are about the same. There are open source implementations of both (but not sure about Java). Since you like Java, you may also like very much Jose:
http://jose-chess.sourceforge.net/

You can use it as a test interface for your engine.

I look forward to some more help.

Thanks again,
Abhay Kumar

[Pallav Nawani]

Hi,
Thanks for all the replies. I wasn't expecting such great help in such a short time!
I checked the links and found them to be quite useful, especially the gamedev.net link.
I would like to know If it's possible that if I write in Java, then I would be able to implement the winboard protocol.
Any good books you know for programming that you want to recommend? And how tougher is to build your own interface?
I look forward to some more help.
Thanks again,
Abhay Kumar

(a) How much time do you have to implement your project? All depends on that. Don't try to do so much that you can't finish it in time.
(b) Don't make all your text bold. We can read normal text.
(c) What is a good programming book for you? Depends on how much you already know. Without knowing that, it is not possible to reccomend a book.
(d) The gamedev link reccommends MTDF over NegaScout, but you don't need to use either, you can get away with simple alpha-beta. Also, his code is probably buggy.
(e) Building interfaces is easy, but tedious, and takes a lot of time. Designing a good interface is hard, however.

As I said, all depends on the amount of time you have. This is the one thing that trips most final year projects
Pallav

[Anonymous]

(a) How much time do you have to implement your project? All depends on that. Don't try to do so much that you can't finish it in time.
(b) Don't make all your text bold. We can read normal text.
(c) What is a good programming book for you? Depends on how much you already know. Without knowing that, it is not possible to reccomend a book.
(d) The gamedev link reccommends MTDF over NegaScout, but you don't need to use either, you can get away with simple alpha-beta. Also, his code is probably buggy.
(e) Building interfaces is easy, but tedious, and takes a lot of time. Designing a good interface is hard, however.

As I said, all depends on the amount of time you have. This is the one thing that trips most final year projects
Pallav

Hi,
Thanks for the info.
My project is of about 1 and 1/2 months duration,atmost 2. So I would like to buld a decent engine that will be strong but no very advanced.

I think I would have to do it in C/C++ since it is hard to make a strong chess program in Java. However I haven't programmed in C/C++ for almost 2 years, I program mostly in Java these days.

I would like a book in C/C++ that also have the basic concepts as well as the advanced topics.

As you said, if I implement Alpha-beta, will it be a strong program. And if I use any other algorithms will it save my work and make the program better? What do you recommend.

[Rémi Coulom]

Hi,
Thanks for the info.
My project is of about 1 and 1/2 months duration,atmost 2. So I would like to buld a decent engine that will be strong but no very advanced.

I think I would have to do it in C/C++ since it is hard to make a strong chess program in Java. However I haven't programmed in C/C++ for almost 2 years, I program mostly in Java these days.

1.5 month is extremely short to write a first chess program. Under these conditions, you should definitely do it in Java. The time you would lose learning C/C++ and struggling with all the segmentation faults would be too long. It is very possible to write a decent chess engine in Java.

R?mi

[Pradu]

You can make a simple engine in a weekend (if you work all weekend) but it is the learning processes that takes the most time. The only thing you would need to research is minimax then the alphabeta algorithm. Learning the concepts (espically alphabeta) was difficult for me. Implementing them is quite difficult too for the first time. Here I suggest a set of goals you might want to go through.

Research Process:
1) Know your programming language well.
2) Research AlphaBeta and know it really well.
3) Research the Winboard Protocol and ways to implement it.

Implementation Process:
1) Create a board structure
2) Create a move structure
3) Create a makemove() & takeback()
4) Test your makemove() & takeback() with hardcoded moves
5) Write a move-generator
7) Write perft to test your makemove() & takeback() and the movegenerator.
8) Write minimax
9) Write alphabeta

And you are done with your program.

One hint that greatly helped me when writing my chess program is using divide to do perft tests. Some engines implement the divide which gives data on the perft of every move that can be made from the current position.

http://homepages.caverock.net.nz/~peter/perft.htm - some perft results for positions

http://witz.sf.net/Other/Witz.exe my in development chess program that does not play chess yet but has implemented perft and divide

just type xboard then divide depth or perft depth
you can setup the board position by using setboard [FEN]

I believe another program called Sharper implements divide and perft as well:
http://www.albert.nu/programs/sharper/main.htm

[Pallav Nawani]

Hi,
Thanks for the info.
My project is of about 1 and 1/2 months duration,atmost 2. So I would like to buld a decent engine that will be strong but no very advanced.

As you said, if I implement Alpha-beta, will it be a strong program. And if I use any other algorithms will it save my work and make the program better? What do you recommend.

You have very little time. You shouldn't worry about writing a strong engine, as if you come up with something with the strength of Tscp, that will most likely beat 99% of humans!

So, Use the language you know best. You don't have the time to write a GUI, drop that idea. Write a simple but *tested* engine, your engine should not make any illegal moves! Don't worry about strength, just ensure that your engine works correctly. Don't try to be clever or sophistcated, just do the things in simplest possible manner. Later, if you feel like it, you can always improve it!

Once you've gotten your perft working, you can modify the perft code to directly go to alpha-beta, its easy! That's how I do it, anyways.

[Anonymous]

You can make a simple engine in a weekend (if you work all weekend) but it is the learning processes that takes the most time. The only thing you would need to research is minimax then the alphabeta algorithm. Learning the concepts (espically alphabeta) was difficult for me. Implementing them is quite difficult too for the first time. Here I suggest a set of goals you might want to go through.

Research Process:
1) Know your programming language well.
2) Research AlphaBeta and know it really well.
3) Research the Winboard Protocol and ways to implement it.

Implementation Process:
1) Create a board structure
2) Create a move structure
3) Create a makemove() & takeback()
4) Test your makemove() & takeback() with hardcoded moves
5) Write a move-generator
7) Write perft to test your makemove() & takeback() and the movegenerator.
8) Write minimax
9) Write alphabeta

And you are done with your program.

One hint that greatly helped me when writing my chess program is using divide to do perft tests. Some engines implement the divide which gives data on the perft of every move that can be made from the current position.

http://homepages.caverock.net.nz/~peter/perft.htm - some perft results for positions

http://witz.sf.net/Other/Witz.exe my in development chess program that does not play chess yet but has implemented perft and divide

just type xboard then divide depth or perft depth
you can setup the board position by using setboard [FEN]

I believe another program called Sharper implements divide and perft as well:
http://www.albert.nu/programs/sharper/main.htm

Thanks for your insights, but what actually is a perft? I haven't heard of it till your message.
And what is the common process for making a move generator?
I would also very much like to include an opening book.

Haven't found the time to check your program yet.

[Sven Schüle]

7) Write perft to test your makemove() & takeback() and the movegenerator.

Thanks for your insights, but what actually is a perft?

Hi Abhay,
follow the link provided by Pradu in his item no. 7 to learn more about "perft".
Sven

[Roman Hartmann]

I believe another program called Sharper implements divide and perft as well:
http://www.albert.nu/programs/sharper/main.htm

My program (Roce) hast that feature too. Especially divide is very usefull to track bugs down!
I had so many bugs in my movegenerator that I even added some functionality to run perft and check for bugs automatically (reads an epd file and checks the precalculated perft values with the calculated ones).

Roman

[Jaime Benito de Valle]

Pradu wrote:


I believe another program called Sharper implements divide and perft as well:
http://www.albert.nu/programs/sharper/main.htm


My program (Roce) hast that feature too. Especially divide is very usefull to track bugs down!
I had so many bugs in my movegenerator that I even added some functionality to run perft and check for bugs automatically (reads an epd file and checks the precalculated perft values with the calculated ones).

Roman

My engine Ayito has the same features as well. Below you can find an automated perft test that I run every now and then just in case. If you can get these figures, chances of having a bug in move generation and/or make and unmake are indeed low.

do{
if (!SinglePeftTest(c++, 4, 1066400,"r1b4r/p2p1ppp/1ppbn2k/4P2P/1PB5/2P2PP1/P7/RNKQ3R w - -")) break;
if (!SinglePeftTest(c++, 4, 1233636,"1q5k/8/1p2n3/p1p1rb2/2Pp3n/PP1P2P1/3B1R2/2R2QK1 b - -")) break;
if (!SinglePeftTest(c++, 4, 1240989,"r3kb1r/pp1bpppp/8/5n2/4n3/4B3/PPP2PPP/RN1K1B1R w kq -")) break;
if (!SinglePeftTest(c++, 5, 1745545,"8/PPP4k/8/8/8/8/4Kppp/8 w - - ")) break;
if (!SinglePeftTest(c++, 4, 1797968,"r3r2k/pp2qp1p/5pb1/8/4P2Q/3PBP2/PP4P1/R2K3R b - -")) break;
if (!SinglePeftTest(c++, 4, 4085603, "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -")) break;
if (!SinglePeftTest(c++, 4, 4466732, "r3k2r/1P1p2P1/1q6/4P3/4p3/6Q1/1p1P2p1/R3K2R w KQkq - 0 1 ")) break;
if (!SinglePeftTest(c++, 6, 11030083,"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -")) break;
if (!SinglePeftTest(c++, 5, 11677860, "R6R/8/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - ")) break;
if (!SinglePeftTest(c++, 5, 29014483, "4r1k1/p1p3pp/1bp3r1/5p2/1P6/2PQ1P1b/R2P1P1P/2B2R1K w - -")) break;
if (!SinglePeftTest(c++, 6, 55577643, "3rr1n1/2qb2p1/2p1pk1p/1p3P2/3P1R1Q/1pP5/P5PP/4R1K1 b - -")) break;
if (!SinglePeftTest(c++, 5, 126222830, "1r4r1/1ppn2pk/p1npq2p/4Pp2/P4p1Q/2PBB2R/1PP1KP1P/6R1 w - f6")) break;

end=1;
}while (false);

Regards,

[Pradu]

... but what actually is a perft? ...
And what is the common process for making a move generator?
I would also very much like to include an opening book...

Perft is a deterministic type of search used to test the move generation and tree traversal code in a chess program. There are two kinds of perfts: perft that counts only the number of leaf nodes and perft that counts all the traversed nodes including the leaf nodes.

Your move generator method really depends on how you set up your board structure. Two of the simplest methods I know are ones using 0x88 and rotated bitboards (if anyone here know any simpler please post). The learning curve for rotated bitboards is very high and has difficult initial implementation, but I'm sure its possible to learn and implement its concepts within a week. IMHO, in the long run using rotated bitboards will become simpler than using 0x88 but then again you have only 1.5 months correct? I suggest using the 0x88 method of generating moves because you can implement it faster and without much research.

There really aren't any good references for learning about bitboards on the internet AFAIK. The "best" online one I found is the one by Prof. Bob Hyatt. Although some diagrams have some inconsistencies (Figure 6) and some important topics aren?t discussed (never talks about how to handle captures, and how to generate moves[sq][256]), it is the most reliable source online and should be good enough to learn the concept and let you figure out the details yourself. My incomplete new engine uses rotated bitboards and you can find the source to it here. My old but buggy engine (It was just to familiarize myself with chess programming and so I didn't bother fixing some bugs) uses 0x88 and can be found here.

Links
0x88 - http://www.seanet.com/~brucemo/topics/topics.htm
rotated bitboards - http://www.cis.uab.edu/hyatt/bitmaps.html

My implementation of opening books will involve hash tables so hopefully someone else here with a different method can answer your question on that.
-----
Wow Jaime, you sure do hate goto's don't you . Nice idea for that piece of code without goto's though.

[Eduardo Waghabi]

Bruce Moreland?s site has changed to http://www.brucemo.com/compchess/programming/index.htm, but the old URL is still up and running, though without many of the new topics.

This forum?s main page has this link and many others under the ?Theory and Programming? topic. Just scroll the page down.

TSCP implements bitboards with an easier move generation than rotated bitboards. But with less than 2 months and no chess programming knowledge, I wouldn?t recommend getting even close to bitboards.

Some years ago, when I first thought about writing a chess engine, I remember this nice James Swafford website, ?Creating the Digital GrandMaster?. Do you know whatever happened to this site?

[Pradu]

It used to be http://www.galahadnet.com/chess/chessprg/ apparently but the website seems to be shutdown.

[Uri Blass]

Bruce Moreland?s site has changed to http://www.brucemo.com/compchess/programming/index.htm, but the old URL is still up and running, though without many of the new topics.

This forum?s main page has this link and many others under the ?Theory and Programming? topic. Just scroll the page down.

TSCP implements bitboards with an easier move generation than rotated bitboards. But with less than 2 months and no chess programming knowledge, I wouldn?t recommend getting even close to bitboards.

Some years ago, when I first thought about writing a chess engine, I remember this nice James Swafford website, ?Creating the Digital GrandMaster?. Do you know whatever happened to this site?

There is a mistake here.
TSCP does not use bitboards.

I do not recommend tscp but for different reasons.
It has a lot of global variables and I think that it is not the best way for starting a chess program.

Uri

[Pradu]

There is a mistake here.
TSCP does not use bitboards.

I do not recommend tscp but for different reasons.
It has a lot of global variables and I think that it is not the best way for starting a chess program.

Uri

I do agree TSCP isn't that great but what else is there for the new programmer?