This is a read-only archive of the old Scratch 1.x Forums.
Try searching the current Scratch discussion forums.

#26 2012-08-25 23:52:12

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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.  sad

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)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#27 2012-08-26 09:51:40

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

Does this use pruning? Ex. Stop calculating a node when its obvious its going to be a bad move. PS. Enable the 2 ply for the people who are beginners (not me).


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#28 2012-08-26 10:28:52

benjamin2
Scratcher
Registered: 2008-10-18
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

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

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  big_smile


http://i.imgur.com/gp6tZ.gif

Offline

 

#29 2012-08-26 12:13:16

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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.

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.)

Last edited by BoltBait (2012-08-26 15:25:16)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#30 2012-08-26 16:07:38

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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.


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#31 2012-08-27 18:12:32

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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.

Thanks.  I doubt that I'll be making the chess engine any more complicated.  It is working well for most people and adding pruning would be somewhat complicated.

I think the next step for me would be to increase the size of the Opening Book.


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#32 2012-08-28 15:22:39

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#33 2012-08-28 15:30:33

maxdoss
Scratcher
Registered: 2010-07-27
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

Funny, because The Turk was fake.


It's my birthday. Deal with it.

Offline

 

#34 2012-08-28 16:41:10

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#35 2012-08-28 17:04:41

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

Molybdenum wrote:

BoltBait wrote:


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.

Cool, you're doing AB pruning. Can't wait for a 5 or 6 ply engine (or more?)!


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#36 2012-08-29 13:52:03

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#37 2012-08-29 16:43:16

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

I started the changes last night.

For Alpha-Beta pruning to be most effective, the potential moves must be ordered first.  It must consider moves that takes pieces before moves that do not.

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!

Aww... Such a good project fell off. Anyway, look at how fast a 4 ply AB is, and maybe implement 5 ply?


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#38 2012-08-29 16:58:45

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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

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

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


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#39 2012-08-29 17:03:21

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

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

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

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

If you get another X% improvement, will you try the 6 ply? And another Y% improvement, 7 ply?


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#40 2012-08-29 17:06:21

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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.


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#41 2012-08-29 17:07:48

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

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.

Well, I meant if it goes a lot faster. If a 7 ply engine still takes 2 days to move, of course you shouldn't implement it.

[60 second rule] is [annoying] ? //True
Also, I did see the knight bug.

Last edited by Molybdenum (2012-08-29 17:08:27)


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#42 2012-08-29 17:16:06

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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.)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#43 2012-08-29 18:14:45

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

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.)

Yes. So I assume even plys are more defensive?


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#44 2012-09-02 03:48:32

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#45 2012-09-02 09:40:28

Molybdenum
Scratcher
Registered: 2012-06-17
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

BoltBait wrote:

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.

Aww  sad


"The Enrichment Center is required to remind you that you will be baked, and then there will be cake."
(|Balls and Platforms: Stay on!|) (|NaOS-H: An operating system... Or is it?|)

Offline

 

#46 2012-09-04 14:06:19

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

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


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#47 2012-09-04 15:07:29

benjamin2
Scratcher
Registered: 2008-10-18
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

That's really clever, I saw piece value coming but I think the idea of pieces in different places being asked different is clever.

I think the reason why odd-ply engines play more aggressively (especially 3-ply) is they don't think about as many opponent moves as they do themselves. The 3-ply doesn't see an attack until the move before it happens, so that can be a real problem, because by then it can be too late to prevent it.


http://i.imgur.com/gp6tZ.gif

Offline

 

#48 2012-09-06 03:00:17

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

New version!

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


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#49 2012-09-08 15:54:03

BoltBait
Scratcher
Registered: 2009-03-09
Posts: 1000+

Re: Challenge The Turk to a game of CHESS!

Another minor update today.

I changed the Moves notation from Coordnate Notation to Algebraic Notation.

Last edited by BoltBait (2012-09-08 18:55:16)


Animated sigs must be banned!
http://boltbait.com/j.pnghttp://boltbait.com/s.pnghttp://boltbait.com/d.pnghttp://boltbait.com/a.pnghttp://boltbait.com/p.png

Offline

 

#50 2012-09-10 17:01:56

eventexception
Scratcher
Registered: 2011-04-08
Posts: 500+

Re: Challenge The Turk to a game of CHESS!

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?

Offline

 

Board footer