Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Chess Game
Author Message
crossley7

Posted: Sun Jun 26, 2011 2:40 pm   Post subject: Chess Game

Well, I finally have functional AI for my chess game so I will now post it here. It isn't great, but playing black against it can be a bit of a challenge from time to time. There are a bunch of other little features I put in, hope you enjoy it.

Chess Game.zip
Description:
Filename:  Chess Game.zip
Filesize:  1.1 MB

apython1992

Posted: Wed Jul 06, 2011 11:11 am   Post subject: RE:Chess Game

This is an impressive start. What algorithm did you use for your AI?

[EDIT]: Sorry for the late post.
crossley7

Posted: Wed Jul 06, 2011 12:41 pm   Post subject: RE:Chess Game

I'm probably leaving it like that since I'm fed up with the repetitiveness of it. I used a custom algorithm of creating a value of possible moves and found the highest scoring move. It is extremely basic and just calculates the value of the square, a piece that is on the square if there is one and if it results in checkmate. It then checks all possible moves for the opponent and takes the highest score from there and subtracts from their move score. It actually plays significantly better than I was expecting, but the worst result a player will have against it will be a draw.
apython1992

Posted: Wed Jul 06, 2011 12:45 pm   Post subject: RE:Chess Game

It builds an entire tree of moves? I have never worked on a chess AI before, but wouldn't that take up way too much memory? Unless you are only looking at the best possible move based on the current turn only (you can imagine the AI would be a lot smarter the more turns it can *predict*, but tree would get exponentially larger for each additional turn you'd like to account for).
crossley7

Posted: Wed Jul 06, 2011 1:49 pm   Post subject: RE:Chess Game

It only calculates for the current move and then the opponents move to follow. If you only take legal moves it is actually about 40 moves within the tree ( I don't store every opponent move, just store the highest value and chack against it repeatedly). For the next move it wipes the whole tree empty and starts over so in terms of memory even with using vectors instead of huge arrays it works really well.

The concept of chess AI is having general values of a move then checking more and more moves so the deeper you look, the more memory, the slower, but the better the ai gets. Once again, like the rest of a chess game it is completely repetition. It felt like I wrote 5 or 6 near identical functions for a few parts of the game but they all had the slightest difference so I couldn't combine them.

If you want to look at my AI code, I can send it to you, just don't want to copy it on here since parts of it are fairly long. I would just need to comment it better if I were sending it off to someone so it would probably be a few hours after I get a chance to look at it until I send the code
apython1992

Posted: Wed Jul 06, 2011 3:22 pm   Post subject: RE:Chess Game

I know how a basic chess AI works (I've thought about implementing my own), I was just curious as to what algorithm you used. Good stuff!
A.J

Posted: Thu Jul 07, 2011 12:14 am   Post subject: RE:Chess Game

Good job crossley7

However, there are a few things you should implement, like 3-fold repetition (which leads to a draw). Based on your description of the algorithm (ths assigning of a heuristic or 'score' to each move, and then evaluating the best moves for yourself and the opponent), it sounds like your are implementing a minimax algorithm. The idea is you play as yourself and the opponent upto a certain number of moves into the future (where each individual moved thought of into the future is called a 'ply', or the depth of your search tree).

Currently, you are only searching one move into the future. However, with a bit of pruning, you can increase this number (take a look at: http://en.wikipedia.org/wiki/Alpha-beta_pruning, and: http://www.glaurungchess.com/lmr.html).

Another cool thing you could do is modify your heuristic in the opening (around the first 10 - 20 moves of the game) by storing famous openings in a database (most modern chess engines do this to save time in the opening). The only downside is that this takes quite a bit of time, and you most likely need a person who is pretty adept at chess to help you out (i.e. 'Google' ).

Good job altogether.
crossley7

Posted: Tue Aug 02, 2011 9:57 pm   Post subject: RE:Chess Game

Ok, well after a nice summer break without coding and a bit of frustration with allegro, I am going to go and fix up a few issues with the program before going back to my allegro program. Should have a new version available within a week provided I don't get overly distracted with other tasks.

crossley7

Posted: Sun Aug 07, 2011 9:53 pm   Post subject: RE:Chess Game

Just did a bit of research on the AI (Had winged it before this point) and I am definitely using a minimax algorithm and am planning on implementing some pruning as well as a better evaluation of the quality of moves.

I had somehow forgotten about 3fold and insufficient material in the code of my original version, but that is now fixed and once I have new AI, I can update the file with the fixed draw detection as well.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 9 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: