Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Chess Game
Index -> Programming, C++ -> C++ Submissions
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
crossley7




PostPosted: 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:

Download
 Filename:  Chess Game.zip
 Filesize:  1.1 MB
 Downloaded:  1032 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
apython1992




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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' Razz).

Good job altogether.
crossley7




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
crossley7




PostPosted: 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:   
   Index -> Programming, C++ -> C++ Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 9 Posts ]
Jump to:   


Style:  
Search: