How do I program chess AI?

Is there anyone who is working on or had done a tutorial on this? I'm not really programming "chess", but I would like to learn how to because it opens up a lot of options for prototyping strategy games on my own.

The way I imagine it is that you store a copy of the board in a 2D array. The values that can be on a spot in the array would be titles for the various pieces to let the computer player, which reads the array to understand the board, know which spaces are occupied and by what.

OK, so far so good. From there, though, you need to get the computer to understand the legal moves. OK, I think I can do that. It'll take some work, but it's just a matter of having a given piece selected and then changing its value on the array... But then there's the issue of having the computer evaluate many possible decisions. That's where I wouldn't know where to start.

Is there anyone who could break it down for me? It'd be awesome if there were already a capx or a tutorial on the topic but it seems very unlikely. Help if you can! Thanks!

well actually as far as i cant tell, a AI that plays chess its really hard... i dont think is doable, unless you use some extrange algorithm, i dont think is possible with standar knowlegde

What exactly do you mean? I'm sure that programming the AI will be hard, but I cannot imagine that it couldn't be done in Construct 2. Difficult is fine. I'm willing to learn. If it is impossible, I'd love to hear from Ashley or a few other veterans before I am willing to write it off completely.

It strikes me that it might be best to make a very simple example capx before jumping into a full game. Here's what I'm thinking: we'll make this educational for the community!

I'll make a miniature version of something like checkers. Then, we'll try to figure out how to make a CPU player. We can use this thread to bounce ideas around and I'll update it frequently with my example. Hopefully in the end we'll get a nice little example file that maybe could be included in later versions of C2 which will show how to program an abstract strategy board game and computer AI.

I'll get to work right now.

I'm sure there are a bunch of internet manuals on how to program a chess cpu. you can take it upon yourself to transcript that into construct.

However i think you're being incredibly naive. programming a chess cpu that that plays on a "human" level, took experts programmers and engineers years and years of research and hard work. So unless you're incredibly good with algorithms and logical thinking and know a ton of math, i recommend you start with something a little bit more doable.

Don't expect that someone will come up with a "oh, just do this" for that kind of request.

Yes, the more I read on it the more unlikely it seems that I'll be able to figure this out in any kind of timely manner... I guess I just figured there are so many apps out there different abstract board games that there must be a straight path to it by now since others have done most of the work. I'm not sure I'm ready to give up on this yet. It seems that learning how to do it would probably be good for my programming knowledge in the long run, even if it takes a long time. I'm seeing some books written on the topic, a couple beginner guides online that aren't much help...

Anyway, if anyone knows something I don't, let me know.

Don't think its easy to make one either, but it could be good training. However you could try something else than to program it an that is to make it learn from experience. Might not be easy either but how it could work is like this.

1. You program all the basic rules for each piece, the ways they can move.

2. You make a system that track all its moves and the player moves.

3. Then at the end of the game if the computer won, you add +1 to all the moves it made, and if it lost you give each move a -1 in relation to what the player moved.

4. And you keep updating this list so each time the computer plays you make it prefer moves that made it win earlier and try new moves if there are only bad ones in the list.

5. Hopefully after a lot and lots of games the computer will be unbeatable as it know all the good moves in any situation....

Whether It works I doubt but could be fun to try.

well, i think he is reffering to a chess game without AI

in that case i think is possible... but not easy

I'm with Sargas on this. It has taken years for teams of engineers to develop AIs and machines that can play chess to a high human standard. It is possible that you could write a very simple chess controller AI that 'thinks' only 1 move ahead, but I expect that designing an algorithm to (for example) permit the loss of a bishop so that in 3 moves the AI might take the opponent's queen would be incredibly difficult. It's something I would also love to be able to do, but chess is such a complex game (and satisfying for it) that you would probably have to spend years tweaking the factors in your algorithm so that it played reasonably well.

I would start with a draughts/checkers game, just to learn where some general boardgame pitfalls might lie and then maybe go for something like chinese checkers.

I'm starting smaller. A simple game with two pawns on either side that capture diagonally-adjacent pieces but can move orthogonally in 4 directions by one tile. To be honest, I don't want to program chess. I just thought that might be the "road most oft traveled" so that's what I asked. And for my purposes, thinking one turn ahead is enough. I'm not trying to make a grandmaster chess engine. I just want a game prototype I'm working on to play with me.

TeacherPeter,

Chess engines work in a few different ways depending on the complexity.

First, as you said, the computer needs to understand it's legal moves. This can be done easily enough by giving each piece a list of valid move offsets from their current location. For example, on an 8x8 board, and counting tiles from the upper left going left to right and then wrapping down to the next row left side (which a 2 dimensional array can model for you) a bishop can move (+/-)n(7) or (+/-)n(9) spaces. You would need to figure out how to define each of these moves and give the pieces the appropriate settings.

Movement is the easy part, the A.I. is where it really gets fun.

Because there are many different ways a chess system A.I. can be written, I am going to just outline a very simple one. For this A.I. all pieces need to have a value so we know what pieces are worth more than the others. Below is how I value my pieces when I play chess. This can be different but I believe this is a pretty common valuation:

1 - king

2 - queen

3 - rook

4 - bishop

5 - knight

6 - pawn

The next step is to define how the A.I. will start a game or act when no piece is in range. Giving a set of random first moves is a good way to start. After the first play, when no valid attacks exist, you could have an aggressive A.I. set itself up for a run on the king. In other words, move a strong piece into an attack position. Or you could move a piece to back up another piece for a more defensive A.I.

Finally, you would want to define the attack strategy rules. At the beginning of each turn, the A.I. needs to evaluate if a piece is in danger. If it is, it should check if it's piece is backed up and if the opposing piece is of greater or lesser value than itself (this is because a piece of greater value will not usually put itself in danger for a piece of lesser value). If no action needs to be taken to protect itself, then it should check to see if it can take any pieces and again, check if the other piece is backed up and if it is higher or lower value. After gathering this list of actions, both defense and offense, the A.I. would need to evaluate which move would be the most productive. Again here you could define if the A.I. is more defensive by backing up or backing off pieces in danger or if it is more aggressive by pressing the attack.

This is of course a very simplified set of instructions but if you can get this to work, then you can look into implementing more advanced A.I. techniques.

I hope this at least gets you a starting point. Good luck with your project.

Hey there! Thanks for that. This is a very interesting way to look at it. I'm sure this is going to be useful.

One brute force way it could be done is have the computer simulate every possible game and build a tree graph of moves to different states of the board. Then once built each move could be rated by how close it is to a check mate. Then the cpu could just pick the move that would result in a win the quickest. A drawback of this is it's not really possible to do this as building the tree graph would be very time consuming and it would take much more memory than is available.

You could instead look n moves ahead instead and choose moves that would lead to a win in n moves or less, but you'd run into the case where there is no win that close so you'd have to use FragFather's idea to have the cpu do better than just a random move. You wouldn't be able to look too far ahead though as the amount of board states to keep track of increases exponentially. Consider as a simplification that there are only 10 moves possible in any given board state. Then with 0 moves you'd have 1 board state to keep track of. With 1 moves 11 states, 2 moves 111 states... So at 9 moves ahead you'd have 1,111,111,111 states to keep track of or a least check for a win. That is over a billion moves and if will were able to store each board state in 64 bytes you'd be using over 64 gigs of memory. So the problem becomes finding some kind of shortcut to make the cpu make a descent decision within the limits of memory and cpu speed. Few would want to play against a computer that took event 10 seconds to make a move. There are shortcuts and simplifications that can be done such as only looking at the better moves per step instead of all of them. That would allow looking more moves away whist using less memory. Also less memory could be used if you only keep the board states as long as it's needed, and mainly keep a move list.

One method that is used to pick a better move is called Minmax. Where the idea roughly is to minimize the player's score and maximize the cpu's score. For this we need to know if one board state is better than another. It's relatively easy to identify a checkmate as a win or lose, but for all the other states we need some kind of rating. One rating could be to sum up the values of the pieces of the board where say the black pieces are: pawn=1, ..king=5, and the white pieces are negative: pawn=-1... king=-5. So after a move if the score goes down then it's better for white and if it's positive it's better for black. For a minimum you'll want at least 2 moves so the opponent's response can be considered as well, and a move can be picked with the best end score.

Another method is the Monte Carlo way. AKA a random set of moves is done and the end score is checked. Usually this is done many times and then only the best result is picked as a set of moves to go with. I imagine this will be haphazard at times but if a high number of iterations (times) is used the results will be better.

Probably a mixture of the methods will be needed to make a good ai that doesn't take forever to decide on a move.

If it's really that complicated though, then how come there are so many strategy game apps with CPU on the various app stores? I mean, I downloaded an app with Latrunculi, Hnefetafl, and 9 Men's Morris all with computer AI, all apparently made by a one man team. Why couldn't it be done easily since it clearly has been done before? Like I said, I don't want to build an amazing chess engine. I just want a game that'll play.

Chess AI is really that complicated. And not one is the same because of who put it together, some are shockingly bad.

There are tons of algorithms available on the net that you will have to implement.

You can copy a open source chess game's ai, or write your own.

Have a look at this.

Ahhh. Judging by this, programming in C2 would produce a very slow AI. Hmm. Thanks for that.