# minmax algorithm in C2 (2d array)

Get help using Construct 2

### » Sun Sep 14, 2014 8:04 am

Hi there,

has anyone experiences with implementing a minmax algorithm (array-based) for a chess game or can give me some advice?
B
43
S
22
G
15
Posts: 387
Reputation: 12,270

### » Sun Sep 14, 2014 8:17 pm

not one?
B
43
S
22
G
15
Posts: 387
Reputation: 12,270

### » Sun Sep 14, 2014 8:51 pm

What have you done so far? First would be a way to score the board, so the algo can know what is good or bad. One simple idea would be to add 1 for each white piece and -1 for each black. So then you could loop over all the possible player moves and pick the move with the best score for that player. You could look more moves ahead so the cpu chooses a better move, but the computation time will exponentially increase.

You can actually impliment the algorithm exactly like in wikipedia. The tricky bit will be generating the list of moves from the game state. I did a chess game and didn't get to ai since I'd need to vastly rewrite it.
B
95
S
34
G
128
Posts: 5,493
Reputation: 81,674

### » Mon Sep 15, 2014 5:41 am

Yes thanks. I know the theory of minmax but i have no idea how to implement this with C2.
Function stack is very low in C2 so recursions is not the right way.
B
43
S
22
G
15
Posts: 387
Reputation: 12,270

### » Tue Sep 16, 2014 4:03 am

@mercuryus
Well I finally took a crack at it and it appears to be working. I wanted to go for a simpler game so I went for checkers instead of chess, and even then I didn't add all the rules. Mainly it lacks kinging and any winning conditions.
https://dl.dropboxusercontent.com/u/542 ... imax2.capx
Not exactly simple but it only has 85 events total. The minimax algo takes up about 12 of them. The rest are for things such as generating move lists, moving pieces and saving and loading the board state from a stack.

It is a tad slow on my machine with 8.5 seconds for a minimax depth of 3. Rest assured it isn't the function object that is slowing it down. The main culprit is the save and restore functions and the generate moves function in the minimax function. It can be made faster i'm sure, but I'm done with it right now.

-cheers
B
95
S
34
G
128
Posts: 5,493
Reputation: 81,674

### » Tue Sep 16, 2014 4:40 am

@R0J0hound

I will try to understand your solution.
....
hmmm - without description very hard to understand what you are doing.
C2 debugging is also crap so....
Nevertheless good work, congrats.
...
 finally i got it.
Calculated the number of possible moves of the chessmen I think C2 isn't the best choice for minmax with chess.
Anyhow I'll give it a try - I think about not to use strings but an array of possible x/y-move and a move-step-index per pawn.
B
43
S
22
G
15
Posts: 387
Reputation: 12,270

### » Tue Sep 16, 2014 4:07 pm

@mercuryus
Updated it with a small change and now it takes about a second less time. Now instead of loop{save->minimax->restore} it does save->loop{minimax->peek}->discard.

With algorithmic code like this you can implement it in JavaScript and get a 10x speed increase.
B
95
S
34
G
128
Posts: 5,493
Reputation: 81,674

### » Thu Sep 25, 2014 7:02 am

...I've forgot to say thanx @R0J0hound

Thank you!
B
43
S
22
G
15
Posts: 387
Reputation: 12,270

### » Thu Apr 27, 2017 1:39 pm

@R0J0hound can you make the source code public again? thanks
"If you want to move a mountain tomorrow, you should start by lifting stones today."
B
65
S
15
G
3
Posts: 293
Reputation: 7,250

### » Thu Apr 27, 2017 5:30 pm

B
95
S
34
G
128
Posts: 5,493
Reputation: 81,674

Next