How do I program chess AI?

Get help using Construct 2

Post » Sat May 03, 2014 11:03 pm

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!
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Post » Sat May 03, 2014 11:44 pm

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
B
23
S
6
G
3
Posts: 316
Reputation: 3,461

Post » Sun May 04, 2014 1:32 am

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.
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Post » Sun May 04, 2014 2:30 am

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.
B
43
S
12
G
6
Posts: 446
Reputation: 6,802

Post » Sun May 04, 2014 2:37 am

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.
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Post » Sun May 04, 2014 2:50 am

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.... :lol:

Whether It works I doubt but could be fun to try.
B
44
S
11
G
2
Posts: 1,182
Reputation: 6,828

Post » Sun May 04, 2014 3:05 am

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

in that case i think is possible... but not easy
B
23
S
6
G
3
Posts: 316
Reputation: 3,461

Post » Sun May 04, 2014 3:10 am

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 only occasionally visit - I'm learning C# for Unity, but c2 is still a respectable game engine imo....
B
73
S
19
G
66
Posts: 2,198
Reputation: 42,193

Post » Sun May 04, 2014 3:32 am

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.
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Post » Sun May 04, 2014 6:37 am

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.
B
38
S
12
G
11
Posts: 331
Reputation: 7,712

Next

Return to How do I....?

Who is online

Users browsing this forum: troxx and 1 guest