Fastest chess?

[Mich Robinson]

We've had many posts on chess lately. One even pointed out a guy who wrote a chess program in 6 weeks. I like game programming but had always steered clear of chess because of the time need to program it. Monday night I suddenly had a brainwave - I lay in bed thinking about data driving the whole thing - it seemed doable & it would save a lot of coding.

Next morning I started to write a move generator just to test my idea out - 4 hours later it was generating all the moves. I was on a roll! A few hours later it was scoring positions in a simple way and playing moves against itself on the terminal. I was elated! I turned it into an applet and wrote a very simple interface in the evening. I pulled the graphics of one of the threads mentioned above.

I played my first game against it at 10pm - it didn't understand castling, en passant, opening theory or even when a game has finished but it played. I think I've written the fastest (in development time) chess program ever I'll spend the rest of the day on it and add a few features but then I'll need to rename it 48hour Chess.

I'm actually feeling rather amazed it all came together so quickly. Feel free to give it a game but don't expect it to play like Kasperov


Play 48 Hour chess

[Luigi Plinge]

Nice job! It doesn't play too badly... although in our game it pretty much gave its pieces away. Then it didn't recognize when I'd checkmated it and let me take its King on the following move. Are you going to add some enhancements like showing which pieces have been taken, and a move list?

[Mich Robinson]

I'm mostly just fixing bugs at the moment I'm trying to get the checkmate detection part working now. The castling rules it follows are currently very poor. Any giving away of pieces is likely to be a bug unless it's trying to push a checkmate out of it's field of vision (horizon effect). I'd like to improve the evaluation but it's a trade off on time taken. Alpha beta pruning needs adding.

Many thanks for playing it though.

[Mich Robinson]

Many of the bugs have been removed.
It plays quite a bit stronger now I think (I could be biased).
Most levels play immediately but level 6 takes around a minute.
Feedback welcome as always.

[Luigi Plinge]

I didn't realise there were different difficulty levels - I just played it on whatever the default was.

Is there a way to get it to load the latest version? I just played it again and it still moved after checkmate, but it didn't take long to load so my browser had probably cached the old one.

Would be nice if when playing as White, the board turned round.

[Mich Robinson]

It shouldn't cache things because I specified no-cache on the html page but I could be wrong.
Try clicking reload while holding the shift key down to get a fresh copy.

Click the image of the brain to change the levels.
The board orientation can be swapped by clicking the little image next to it.
You can also see board coordinates now.

Thanks for the feedback.

chess

[Luigi Plinge]

Firefox is definitely caching the old version. Shift + reload didn't help.

So I tried it in IE instead... Checkmate!!! (ummm... not it's not!)

[Mich Robinson]

Checkmate - well it is next move but that is on my list of bugs (as is the full rules of castling and en passant). Maybe it would be easier if I just changed the message to "Checkmate next move".
EDIT: actually that's happening just after your move so it does need fixing - damn!

I note you haven't upped the level - everything up to 5 should play reasonably quickly while can 6 take around a minute (on my old machine). I'm looking into improving the performance and trying to decide what more to add to the evaluation process. Obviously it's a trade off between time spent evaluating a position and time spent scanning the tree.

[emilio rossi]

nice job:)
but you should set a promote piece selection since i may not want to promote always in a queen..

[Mich Robinson]

I've added your suggestion to my list. I can't remember the last time I queened a pawn and wanted anything other than a queen though

Also just released a new version which plays better and quicker, I've also added more levels and a progress bar (it's quite addictive doing this stuff).
You may need to force a reload in your browser.

[Ogeh Ikem]

I can't remember the last time I queened a pawn and wanted anything other than a queen though

Sometimes, promoting to a knight will lead to an immediate check or even checkmate, whereas promoting to a queen wont.

[emilio rossi]

it happened to me once, i was compelled to promote not in a queen because it would have been a stalemate:)

[Mich Robinson]

Sure but I have a limited amount of time to develop these things (kids, wife, tennis, swimming etc). I have added the request to my list of "things to do" but the main aim is to get it to play ok first. Perhaps an even higher priority is to actually get it to know when it's won or lost

I promise I will add the feature and am very willing to listen to any suggestions anyone has.

[Mich Robinson]

Latest version (d6.1) adds:
* Better play
* Sound
* Drag and drop pieces
* En passant
* Game history if you click the "history" pawn

Chess

[Arun Giridharan]

Mich Robinson wrote:Latest version (d6.1) adds:
* Better play
* Sound
* Drag and drop pieces
* En passant
* Game history if you click the "history" pawn

Chess

There is Tooo much Bug in your program, it won't accept checkmate rather it says stalemate.

[Mich Robinson]

Arun Giridharan wrote:There is Tooo much Bug in your program, it won't accept checkmate rather it says stalemate.

I'll admit I make changes to the program quite often so it's quite likely a bug has crept in (these chess programs are quite complicated). Thanks for alerting me - I'll find out what it is and fix it soon. Are there other bugs you noticed?

[Arun Giridharan]

Mich Robinson wrote:Are there other bugs you noticed?

First : It makes same set of moves again and again no AI(bug1).
Second: Because of no AI it's easy to beat from [1 to 10 IQ]
Third : It never accepts Checkmate , during the proccess of checkmate something bad happens ( sometime i don't see my King magic bug)
Fouth:Rest is pretty good, i got inspired .

thank you

[Mich Robinson]

Arun Giridharan wrote:First : It makes same set of moves again and again no AI(bug1).

It picks openings from a library of 1000 openings. There shouldn't be that much repetition. If it finds moves that it thinks are equally good then it will pick randomly between them. I played a couple of short games against it and it didn't make the same move twice.

Arun Giridharan wrote:Second: Because of no AI it's easy to beat from [1 to 10 IQ]

At the moment it plays somewhere around ELO 1500 (I think) which is a middling chess club player. To make it play even at that level requires quite a lot of AI. I'm finishing a couple of small projects at the moment but my aim after that was to improve the strength of the chess program - I really wanted it to play at around ELO 1900 - 2000 but also keeping it fun to play.

Arun Giridharan wrote:Third : It never accepts Checkmate , during the proccess of checkmate something bad happens ( sometime i don't see my King magic bug)

I'm looking into this.

Arun Giridharan wrote:Fouth:Rest is pretty good, i got inspired .

Thank you.

PS What is your chess rating? Have you written a chess program yourself?

[Stephan van Hulst]

Hi Mich,

If I may comment on your coding style, you will be a lot less likely to introduce bugs if you get rid of all the static fields and constants. Don't use static fields. And instead of all the int and String constants you're using, use enums instead. About all the arrays you've got hardcoded, it may be preferable to read their contents from a file.

I would also refactor the paint() method, which is an absolute leviathan. Although you mentioned you might have used another's version?

Overall, try to break everything up in more classes that handle separate responsibilities.

[Mich Robinson]

Stephan van Hulst wrote:Hi Mich,

If I may comment on your coding style, you will be a lot less likely to introduce bugs if you get rid of all the static fields and constants. Don't use static fields. And instead of all the int and String constants you're using, use enums instead. About all the arrays you've got hardcoded, it may be preferable to read their contents from a file.

I would also refactor the paint() method, which is an absolute leviathan. Although you mentioned you might have used another's version?

Overall, try to break everything up in more classes that handle separate responsibilities.

Thanks for the comments sadly I code in many different languages and I find it quite difficult keeping up with the best practises in each one. The bugs though are less to do with coding style though and more because chess is quite complex to program well. You need to prune the search tree quite dramatically to have any success - sadly the methods used are all very very new to me - I'm reading books, reading others experiences on the web, trying to understand and coding at the same time - this doesn't lead to reliable code!!! It doesn't help that whatever you do just causes a subtle switch in the search tree at 4 moves deep rather than causing the program to error so it's difficult to know whether a change has improved the program or not. Often a change might help in say some pawn vs king endgame but then subtly screw up the midgame. I can certainly see why many chess programmers just alter an existing program rather than code from scratch.

I do have a new version of the program but I have barely tested it at all - perhaps over Christmas. I'll try to incorporate your ideas at the same time.

[Arun Giridharan]

Mich Robinson wrote:
PS What is your chess rating? Have you written a chess program yourself?

I'm a FIDE MASTER , No ,Not yet.

I forgot to say there is no En passant move.

[Arun Giridharan]

Mich Robinson wrote:

Arun Giridharan wrote:Third : It never accepts Checkmate , during the proccess of checkmate something bad happens ( sometime i don't see my King magic bug)

I'm looking into this.

It accepts checkmate, thanks.

[Arun Giridharan]

But still there are lot of bugs in the middle game.

[Arun Giridharan]

Mich Robinson wrote:
At the moment it plays somewhere around ELO 1500 (I think) which is a middling chess club player.

No, ELO 1500 player play much better than this ,if you ask me it might be 900-1000 or 1200 (my guess).

[Mich Robinson]

Arun Giridharan wrote:I'm a FIDE MASTER

Impressive! I don't think my program will get to 2300 even if I get my planned changes working.

Arun Giridharan wrote:I forgot to say there is no En passant move.

The program certainly used to play en passant and I'm not sure why this would change. My bug list is starting to expand

Arun Giridharan wrote:But still there are lot of bugs in the middle game.

By bug do you mean it does something illegal or do you mean it just makes a bad move. Unfortunately the issue I'm having with pruning the search tree is pruning far too much and the program then has to decide between the moves it's left with. I was a little frustrated trying to fix it last time and put the project on the back burner. Hopefully when I clear this bug it will start to improve dramatically. Unfortunately I'm only a moderate chess player so there's only so much I can add. If you have the time to occasionally play the program then I'd appreciate any suggestions on how to improve the program.

Arun Giridharan wrote:No, ELO 1500 player play much better than this ,if you ask me it might be 900-1000 or 1200 (my guess).

I'll have to bow to you on this though it was regularly beating players ranked up to 1500 over the internet but their ratings could be inflated.

Arun Giridharan wrote:It accepts checkmate, thanks.

Strange - I haven't changed anything yet

[Arun Giridharan]

Mich Robinson wrote: If you have the time to occasionally play the program then I'd appreciate any suggestions on how to improve the program.

Sure , Note down another bug it accepts checkmate even before checkmate, pretty awesome .

[Mich Robinson]

Arun Giridharan wrote:

Mich Robinson wrote: If you have the time to occasionally play the program then I'd appreciate any suggestions on how to improve the program.

Sure , Note down another bug it accepts checkmate even before checkmate, pretty awesome .

I have found the bug in the en passant and have fixed it in development. There is currently an issue in the tree pruning which I've already mentioned and this is causing all the checkmate/stalemate issues and most of the bad move issues. It's very kind of you to tell me about bugs as this allows me to fix them, I also appreciate any constructive suggestions on making the program better however you'll stand on firmer ground regards the sarcasm when you've had a go at writing a chess program yourself.

[Ralph Cook]

I find the criticisms that I've read so far a little harsh. In my limited experience, Master level chess players usually rate low-to-mid level chessplayers worse than they actually are. It is very tricky to rate a chess player or game from playing it a few times, especially a computer chess playing game if one is not very familiar with the kinds of things such games often do. Less-powerful chess programs still do some things better than roughly-equivalent human players, and some things much worse. Bottom line: don't take the 800-900 rating estimate too seriously.

As for coding style, I can't comment on it (haven't found a link to the source yet). I will say there is a tendency among some people to label particular practices 'bad' (or maybe 'BAD') without regard to what they're being used for, and I think this is myopic. Static fields and constants are not 'BAD' in and of themselves; they have particular characteristics that makes them useful for some things. They are also misused by some programmers, and, when misused, can make it easier/more likely to cause a bug, and even a hard-to-find bug, than equivalent non-static constructs.

I regard statics as a case where, when I'm using them, it is good to know exactly why they are better than a non-static construct, and to take extra care that their use does not cause side effects that are not obvious to the program reader.

That being said, there is another factor here: chess programs are exceptionally high users of CPU and memory. To take your program and raise its prowess by a few hundred points is likely going to take a lot of both. It is also likely to be handling things loops in a way most of us programmers never have to deal with: millions and millions of loop iterations, with a time limit measured in minutes or seconds. While in those loops, it makes a LOT of sense to limit object construction, which is a CPU-intensive operation in Java at the lower level. Again, I haven't seen the code, am not commenting on the specifics, but if there are values that can be held in statics in those lower levels, it might make perfect sense. It would certainly be better than constructing objects at that level, and may even be better than using an instance reference -- I don't remember that much about all the jump tables java goes through for instance references vs statics.

My point really is that a chess-playing program has unusual constraints, and that makes it even more advisable to evaluate what constructs to use rather than just say "statics are 'BAD'".

I think it would add a lot to show the piece while it's being dragged. I have some code somewhere that does that, if you're interested. And if there's a link to the source you could send me privately, I'd be interested in that as well.

rc

[Stephan van Hulst]

In my experience, it's useful to start learning that certain practices are 'evil', and should only be used when you have a sound reasoning for why you are using them.

Besides, even if statics made the program faster (which I sincerely doubt), it wouldn't be advisable to make such an optimization before performing benchmarks and figuring out where the bottlenecks in a program are.

I agree that chess programs work within difficult constraints, but this is still no reason to throw standard practice out of the window before you have properly tested.

I should note that I can't really comment on the implementation of methods, because I decompiled the class file. But what stood out was that there were only two class files for an entire graphical chess program, one of which takes way too much responsibility, has oodles of static fields and constants with hard names. My point is that if you're going to write a program in Java, you should probably use good Java practices. If speed is your only concern, you might as well write in C.

[Mich Robinson]

Stephan - I took your comments on board and have already started to make changes where feasible. The main issue with this program has been trying to learn new concepts on manipulating game trees - I actually thought I was pretty good at this stuff so it came as a shock to find. Then there's the issue of coding these idea. Then I had to work out whether what I'd coded was correct - it wouldn't be too bad if it just failed but instead I just get moves that look a little doubtful in certain positions. Sure I can work my way through a log of approx 1m moves to analyse it's decisions but life's too short.

At the moment I'm pretty sure the issue is with extending the search for all takes but I'm also using fractional extensions and occasionally not looking far at all if standing pat and doing nothing looks better. I find this stuff quite complicated and find I have to remind myself why I'm doing it and what is supposed to happen. The idea of learning/using the best coding practise takes a bit of a back seat.

I fully understand your point about writing the code correctly first and then tuning it later. Sadly I just write it in the way that comes naturally first and then try and improve things later when I have time. I would actually love to write this in C just because C would give me a 10x speed increase but sadly no-one would be able to play the program unless they installed it and that is too big a sacrifice.

[Stephan van Hulst]

Well, my post was more of a response towards Ralph; I realize that you mostly wrote this to see how far you could get as fast as possible. My comments were mostly about Java and OO programming in general.

I once wrote a chess program from the completely opposite starting point. I threw all speed out and wrote the code as if I had no time constraints. That was an interesting experience as well. I had separate classes like Chess, ChessPiece, Color, Move, Player, AI, etc.

I just never wrote an actual computer player implementation for it, which it seems is what your experience is about.

[Mich Robinson]

Ralph Cook wrote:chess programs are exceptionally high users of CPU and memory. To take your program and raise its prowess by a few hundred points is likely going to take a lot of both. It is also likely to be handling things loops in a way most of us programmers never have to deal with: millions and millions of loop iterations, with a time limit measured in minutes or seconds. While in those loops, it makes a LOT of sense to limit object construction, which is a CPU-intensive operation in Java at the lower level. Again, I haven't seen the code, am not commenting on the specifics, but if there are values that can be held in statics in those lower levels, it might make perfect sense. It would certainly be better than constructing objects at that level, and may even be better than using an instance reference -- I don't remember that much about all the jump tables java goes through for instance references vs statics.

My point really is that a chess-playing program has unusual constraints, and that makes it even more advisable to evaluate what constructs to use rather than just say "statics are 'BAD'".

I think it would add a lot to show the piece while it's being dragged. I have some code somewhere that does that, if you're interested. And if there's a link to the source you could send me privately, I'd be interested in that as well.

Ralph
Common sense says it must cost time to pass arrays back and forth between methods. My program might look at a million chess positions before picking the wrong move. Passing the board array back and forth each time would be expensive though I haven't verified this. There are many things you can do to improve matters but, at the end of the day, you have a choice between passing an array back and forth a few million times or just leaving it as a static. The side benefit of the static array is that it is very simple to understand

I'll look into the idea of dragging the pieces and contact you if I run into difficulties - thanks for your offer. My main aim though is till to fix the bugs that Arun mentions and then to improve the playing strength.

[Stephan van Hulst]

Mich Robinson wrote:Common sense says it must cost time to pass arrays back and forth between methods.

Why?

[Mich Robinson]

Stephan van Hulst wrote:

Mich Robinson wrote:Common sense says it must cost time to pass arrays back and forth between methods.

Why?

I know nothing about the internals of Java but this would be my reasoning. In any language I can only see two ways to pass an array:

pass a local copy - obviously means the array must be copied before it can be used. This would take a small amount of time depending on the array size. If the array is passed back then this also takes time. If you then do this a million times for each position visited and then again for each method that wants to use the array then this will definitely add up.

pass a reference to the array - this is obviously faster as you're just passing a reference however in this case I don't see any advantage between doing this and using a static array. I suppose you're hiding your global variable through various references but is that an improvement?

I'm quite willing to be corrected/educated though

[Stephan van Hulst]

Well yes, copying complete arrays costs time. But why would you do this? The only reason I can think of is to make a protective copy of the real board before the computer "tries" moves to see if the outcome would be positive. But this consideration is completely separate from good coding practice.

Passing a reference costs no time at all. Theoretically it might, since the stack frame could contain an extra variable which will be handled by the processor. This duration will be dwarfed by any other aspect of the program, however.

To the compiler and JVM there is absolutely no gain in using a method parameter over a static variable. However, passing arguments dramatically increases the ability to test and debug code and to reason about its correctness. This is important even to something like a chess program. Especially if you don't have any data to support the need for micro optimizations like using global data.

I'm curious however to see how much difference in performance it would make if you take a completely procedural approach versus a more object oriented one. I will dig up the code I wrote, and if you're interested you can port your AI into it. Or if you like, I can take your AI and port it myself.

[Ralph Cook]

Stephan van Hulst wrote:In my experience, it's useful to start learning that certain practices are 'evil', and should only be used when you have a sound reasoning for why you are using them.

Besides, even if statics made the program faster (which I sincerely doubt), it wouldn't be advisable to make such an optimization before performing benchmarks and figuring out where the bottlenecks in a program are.

I agree that chess programs work within difficult constraints, but this is still no reason to throw standard practice out of the window before you have properly tested.

I should note that I can't really comment on the implementation of methods, because I decompiled the class file. But what stood out was that there were only two class files for an entire graphical chess program, one of which takes way too much responsibility, has oodles of static fields and constants with hard names. My point is that if you're going to write a program in Java, you should probably use good Java practices. If speed is your only concern, you might as well write in C.

I do not regard statics as 'evil', though there are certainly uses made of them that are poor engineering. As I said:

Ralph Cook wrote:
I regard statics as a case where, when I'm using them, it is good to know exactly why they are better than a non-static construct, and to take extra care that their use does not cause side effects that are not obvious to the program reader.

which is close to what you said. It appears you regard their use as "violating standard practice", and I don't. So we disagree on that.

And though I agree that optimization is best done after bottlenecks are determined, there is such a thing as designing the program to avoid some things. We all do that, all the time, mostly without thinking about it. And the nature of a chess-playing program is such that designing for speed and memory use is a good idea because of its special needs. It is not easy to refactor everything; some design decisions made up front will percolate through the code, and then changing them is hard and error-prone. It is easier to get those right ahead of time, not to wait for testing.

No one ever said speed is the only concern. I gather he's writing in Java so that it can be played on the web.

[Mich Robinson]

I've managed to fix most of the issues reported. It's playing a bit better but it still isn't playing well yet. Feel free to give it a try (Fun Chess v16.4). I do have a few ideas on how to improve the strength but that will have to wait till Christmas is over.

[Arun Giridharan]

Mich Robinson wrote:I've managed to fix most of the issues reported. It's playing a bit better but it still isn't playing well yet. Feel free to give it a try (Fun Chess v16.4). I do have a few ideas on how to improve the strength but that will have to wait till Christmas is over.

yes, it's playing better.

[Mich Robinson]

Arun Giridharan wrote:yes, it's playing better.

That's good news

[Phil Freihofner]

Mich Robinson wrote:I would actually love to write this in C just because C would give me a 10x speed increase but sadly no-one would be able to play the program unless they installed it and that is too big a sacrifice.

I presume that is a comment about your skill and knowledge of C programming vs your knowledge of Java programming. Well-formed Java is very fast, quite on a par with C. Certainly it is not 10x slower! From what I have read on this thread, your code is pretty monolithic and could probably perform much better using good Java practices. I recommend checking out the "Cattle Drive" here, for example, as a way to achieve this end.

Very cool that you got the game working so quickly! You might check out Ludum Dare competition, for Java games written within 48 hours.

I am an "A" rated chess player, and I wrote a chess game in VBA (Visual Basic for Applications), believe it or not. I did get legal move checking encoded, including castling and en passant, and had some nice "Staunton" bitmap graphics I drew myself for the pieces. But what a ridiculous project! Who is going to buy Access database to run a chess game! This was a few years before I discovered Java. I didn't make a lot of progress with tryin to do minmax, but instead took it in the direction of making a tree structure to help one read chess books. A lot of the explanatory game text is very tedious to play out and then reset the board, but with the program it was easy to "pop" my way back to branching positions. It was fun to write. (I'm the only person I know who implemented click-and-drag icon animation on an Access form. Did not turn out to be a particularly transferable or useful skill. Oh well.)

Anyway, with the game project I've been doing, as part of the learning process, I've gone back and rewritten it 3 times, based on growing knowledge of Java. Each time, orders of magnitude improvements in performance and capabilities. I strongly recommend as a *parallel* activity to invest time in Java study, especially if you plan/hope to pursue making this game a product or do more Java programming.

My two cents. Congratulations on getting minmax working! That is no mean feat.