Today I found KChess, the chess software for Kindle in Amazon. It's built by Oak Leisure Systems Software and is available for $2.99 only.
It has 10 levels of strength, level 1 being the easiest and 10 the strongest. I was surprised to see how good even Level 1 plays. I have won against that after some accurate play and had to play all through a rook end game to win against Level 2. I am now playing against Level 3 and looks like this is the level where I will be stopped for the moment. The app is surprisingly well designed. I wish I could save the games that I play - that's one thing that can be done as additional feature in future release of this app.
I am so happy to get this. This game itself made me think again - Kindle Rocks!
Update: After a few days, I started winning regularly against the highest level (Level 10). I have been playing it now in both my Kindle DX and the new Kindle 3 that I bought for Shusmita this valentines's day.