next topic »

[on:]

Hi All

Here is my little project: A chess game for the Arduino Uno. It uses a graphics LCD as a user interface. Currently the DOGS102 shield and the DOGM128 shield are fully supported.
The chess game will be part of the next release of the dogm128 library. Meanwhile the source is available on request or at the project home page (browse source):

http://code.google.com/p/dogm128/wiki/chess

Including the graphics lib, the complete chess game requires about 12K flash ROM.

Oliver

DOGM128


DOGS102

[Reply #1 on:]

Cool!

[Reply #2 on:]

This is all sorts of awesome combined together to one big dish of awesomeness (sorry...)

Really cool!

[Reply #3 on:]

The pieces look a bit flimsy, but still very good for a board of 64x64 pixels.

If your graphical lib is integrated in those 12 KB of flash, how many bytes did you actually need for the Game ?

Personally I wouldn't know where to start programming and getting it under 16 KB seems a big achievement to me. I don't know whether I'll do something with it, but I'd very much like to have a look at the sketch used.

Most important question... How does it play ?
What response times do you get and is it able to offer you a worthy opponent ?

Two words, Great Job !

[Reply #4 on:]

Most important question... How does it play ?
What response times do you get and is it able to offer you a worthy opponent ?

I presume you have to play against a human opponent.

[Reply #5 on:]

You will play against the ATMEGA. The 12K flash rom contains a full and working chess playing engine.
I will post some more details later.

Reaction is about 2 seconds or so, but I guess that the engine is quite weak (altough I never won against my engine... but this probably only means that I am a really bad player ;-)

For sure, there is room for improvement.

Oliver

[Reply #6 on:]

You will play against the ATMEGA. The 12K flash rom contains a full and working chess playing engine.
I will post some more details later.

Reaction is about 2 seconds or so, but I guess that the engine is quite weak (altough I never won against my engine... but this probably only means that I am a really bad player ;-)

Wow, neat.

Yeah I'd be interested to see some more info!

[Reply #7 on:]

You designed a chess game engine? Bluddy brilliant!

Please do tell us more, we are glued to our various screens! Especially the game engine...how did you start that, if you don't mind me asking. 

[Reply #8 on:]

You designed a chess game engine? Bluddy brilliant!

I agree. I hadn't even considered someone would take on such a task. However if one thinks back
to the early apple II and Z-80 CP/M based computers, there were chess games being sold that worked.

The 328 and 1280 chips are certainly as powerful as those early processors. However with the small amount
of SRAM memory avalible it certainly must have been a challenge?

Lefty

[Reply #9 on:]

Hi All

Here are some values on the program size
  Graphics Lib and Font data: 6 KB
  GUI, Bitmaps and Chess Engine: 5 KB

About the program development:

First I did research on existing chess engines. I found some very
small (regarding code size) engines, but they seem to be very cryptic and still use
a lot of ram. There is also one ATMEGA port of one engine, but I was not
able to understand how to control that engine.

The other issue has been the copyright. Many implementation did not fit to
the LGPL, which had been the intended license for the chess game.

And finally, I wanted a small implementation for the Uno. This requires
some tricks in C...

... so I started writing my own implementation. First step had been to implement
a "legal move finder". Once the program knows all legal moves for a color
and a given board setup, it is quite easy to setup a simple chess engine which
selects randomly a legal move.

I moved on and implemented a simple search algorithm for the best move.
The current algorithm is quite simple: negamax. Best move rating is mainly
based on the material. If you loose a rook, it is rated as a bad move.

Most ideas and links are covered here:
http://chessprogramming.wikispaces.com/

The most important improvement would be to implement alpha-beta search.
But I first wanted something working before that.

Code is here:
http://code.google.com/p/dogm128/source/browse/libraries/Dogm/utility/chess.c

PDE (just a simple wrapper) is here
http://code.google.com/p/dogm128/source/browse/libraries/Dogm/examples/Chess/Chess.pde


Oliver

[Reply #10 on:]

Wow! I might win against a 32KB brain if I try my best. Never learned any techniques in chess. This is very cool! So what happened to the resistor in picture? Too large for back light so you put two parallel?

[Reply #11 on:]

Oh, you noticed that little detail in the picture 
I simply did some experiments with the backlight. The shield is ok, but its documentation according to some specific backlight colors is a little bit incomplete (http://schmelle2.de/wp/arduino/shields/dogm128-shield).

[Reply #12 on:]

Are your engine board or piece focused?

I also wonder it is deterministic; would two identical plays (from the player perspective) cause two equal outcomes?

Do you use well known openings? Or do you use the search from the get-go?


I've also written a simple chess engine as a part of my bachelor degree, the Alpha-beta pruning search is actually the source for my alias (also my initials A.B. aligns well).
Looks cool!
I'll have a look at the source one of these days

[Reply #13 on:]

The evaluation function looks for the number of pieces and how are pieces placed on the board. So I would call this "board focused".

The engine does not use any random function. If you play the same moves, the engine will react always in the same way.

The engine does not have any opening database. So far I did not add anything which was not strictly required... to keep the program size as low as possible.

The Alpha-beta pruning search is the topmost item on my TODO list for the game engine.
However I did not fully understand that algorithm yet, so I am still afraid of its implementation.

This is a list of things which should be added:
1. alpha-beta search
2. dynamic depth/quiescent search
3. end game improvements
4. repetition and 50-move rule
5. better, perhaps piece focused evaluation
6. opening database

Anybody is welcome to contribute to the code at http://code.google.com/p/dogm128/
And I guess Andy (http://arduino.cc/forum/index.php/topic,50524.0.html) still has some S102 shields available for testing the engine

Oliver

[Reply #14 on:]

Cool! Where are the images stored for the chess pieces?