Scratch

I rewrote most of The Turk today and posted version 2.0 for your enjoyment.  I streamlined everything by reducing redundancy and I reduced the total number of scripts by 10%.  I also broke the AI into separate sprites which helps keep Scratch from crashing when making script changes.  Then...

I added a 4-Ply chess engine for those who are patient.  It takes 3-4 minutes per move.

Once in a game, click on the wrench icon to adjust the ply.  You can change it any time it is your turn.

I have noticed that it plays a better game.  I'm just not sure HOW much better.*

Of course, in the process of updating the engine I messed up the En Passant captures. 

EDIT: I fixed it (and a few other bugs including a knight bug) so hopefully everything's working now.

EDITEDIT:  *I did a little research and this is what I found...

A 3-ply engine performs at about 1100-1200 Elo rating and a 4-ply engine performs at about 1200-1400.

For comparison, a "bright beginner" has a Elo chess rating of 1000 and Garry Kasparov (often considered the greatest chess player of all time) had a rating of 2851 at his peak.

Last edited by BoltBait (2012-08-27 18:09:21)

BoltBait wrote:

EDIT: By the way, if you open with the moves for Fool's Mate, The Turk will gladly take your king. 

I think I tried it in the 3-ply and it never took my king. Maybe I didn't.

I will try the 4-ply when I get on a computer instead of my iPad, looking forward to it 

BoltBait wrote:

Molybdenum wrote:

Does this use pruning? Ex. Stop calculating a node when its obvious its going to be a bad move.

No. It looks at every move.

UNLESS The Turk can take your king. In that case it stops thinking and just does it.

A 3 or 4 ply engine is fast enough (even in Scratch) that pruning really isn't necessary.  Now, once you get to 6-ply, maybe.

Well, 4 ply is a bit slow (for me at least), so if you ever have time or extend it to 5 ply, consider pruning.

BoltBait wrote:

Molybdenum wrote:

PS. Enable the 2 ply for the people who are beginners (not me).

EDIT: Forgot to mention... I will not be implementing a 2-ply engine.  I think you'll find that it is simply too weak.  If you're curious what a 2-ply engine performs like, you can try http://scratch.mit.edu/projects/Midecah/569176.  (Warning: his game does not work in turbo mode.)

Oh.

If you haven't clicked 'love it' yet, now's your chance!

Molybdenum wrote:

BoltBait wrote:

Molybdenum wrote:

Does this use pruning? Ex. Stop calculating a node when its obvious its going to be a bad move.

No. It looks at every move.

UNLESS The Turk can take your king. In that case it stops thinking and just does it.

A 3 or 4 ply engine is fast enough (even in Scratch) that pruning really isn't necessary.  Now, once you get to 6-ply, maybe.

Well, 4 ply is a bit slow (for me at least), so if you ever have time or extend it to 5 ply, consider pruning.

I did a little research and it appears that Alpha Beta pruning wouldn't be too hard to implement.  I'll see if I can add it this weekend.  That should speed up the 4-ply engine but I doubt it will be fast enough for a 5-ply engine.

Last edited by BoltBait (2012-08-28 16:53:34)

I started the changes last night.

For Alpha-Beta pruning to be most effective, the potential moves that take pieces must be considered first.

I put those changes in last night.  So, this weekend, I'll just have to implement the actual pruning.

EDIT: and with that, I'm off the front page.  I appreciate your support.  Thanks everyone!

Last edited by BoltBait (2012-08-30 14:46:58)

Yes.  It will all depend on how much better the 4-ply engine performs.

If I get a 10% improvement    I'll stop.
If I get a 80% improvement    I'll see what a 5-ply engine looks like.

I'll know more Saturday when I do the actual coding.

Well, I doubt people want to wait more than... say... 2 minutes for the computer to move.  So, what's the point of writing a 6-ply engine if you have to wait more than an hour per move?

At some point we simply have to look at the limitations of the Scratch language.

An interesting observation: 

Odd-Ply engines seem to play more agressively then Even-Ply engines.*

This is probably due to the imbalance of looking at more moves for yourself than for your opponent.

I'm really curious how AB pruning will perform.

(*Therefore, I'd LOVE to push The Turk to 5-Ply.)

OK, so I implemented the Alpha Beta pruning method and ran some tests.

While it is now ignoring LOTS of moves, the extra code needed to make this happen balanced out any benefit.

Bottom line: There was no speed improvement.

So, with that... I'm back to improving the opening book.


EDIT:

My test results:

3-ply considered 27,538 moves and took 20 seconds.

4-Ply considered 250,433 and ignored 710,495 moves and still took slightly over 4 minutes.

Last edited by BoltBait (2012-09-02 04:03:44)

Since a question came up about my board valuation function, I thought I'd just give some URL's that I used during my research on how to build a chess engine.

Chess Piece Valuations
How to beat a chess computer
Getting Started
Computer Chess
Minimax Algorithm
Alpha-Beta Pruning

New version!

Very minor update.  I only fixed a couple of poor plays it was making.

BoltBait wrote:

Since a question came up about my board valuation function, I thought I'd just give some URL's that I used during my research on how to build a chess engine.

Chess Piece Valuations
How to beat a chess computer
Getting Started
Computer Chess
Minimax Algorithm
Alpha-Beta Pruning

Thanks for sharing!

Is it possible to limit computing time to one minute
and getting better results compared to ply3?