How do I program chess AI?

Get help using Construct 2

Post » Sun May 04, 2014 9:19 am

Hey there! Thanks for that. This is a very interesting way to look at it. I'm sure this is going to be useful.
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Post » Sun May 04, 2014 7:36 pm

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.
B
94
S
33
G
118
Posts: 5,395
Reputation: 75,851

Post » Mon May 05, 2014 11:11 am

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

Post » Mon May 05, 2014 11:32 am

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.
You think you can do these things, but you can't, Nemo!
Just keep reading.
Just keep learning.
B
65
S
16
G
9
Posts: 1,429
Reputation: 12,728

Post » Mon May 05, 2014 11:47 am

Ahhh. Judging by this, programming in C2 would produce a very slow AI. Hmm. Thanks for that.
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Post » Mon May 05, 2014 11:59 am

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


Not really, but it will take you awhile to build it. There was someone in the jobs board that said he had experience with this. Might be a better way to do it? I personally suck at A.I, and rather outsource it, or at least outsource the majority which leaves me to tweak ;)
You think you can do these things, but you can't, Nemo!
Just keep reading.
Just keep learning.
B
65
S
16
G
9
Posts: 1,429
Reputation: 12,728

Post » Mon May 05, 2014 12:03 pm

I'm afraid you're right. Still, I'd like to learn how to do it myself one day, but a mathematician is something I am not.
B
11
S
2
G
1
Posts: 172
Reputation: 1,486

Previous

Return to How do I....?

Who is online

Users browsing this forum: No registered users and 5 guests