minmax algorithm in C2 (2d array)

Get help using Construct 2

Post » 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?
Image Image Image
B
42
S
22
G
15
Posts: 372
Reputation: 12,215

Post » Sun Sep 14, 2014 8:17 pm

not one?
Image Image Image
B
42
S
22
G
15
Posts: 372
Reputation: 12,215

Post » 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
91
S
31
G
103
Posts: 5,235
Reputation: 67,756

Post » 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.
Image Image Image
B
42
S
22
G
15
Posts: 372
Reputation: 12,215

Post » 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
91
S
31
G
103
Posts: 5,235
Reputation: 67,756

Post » Tue Sep 16, 2014 4:40 am

@R0J0hound

I will try to understand your solution.
....
[edit]hmmm - without description very hard to understand what you are doing.
C2 debugging is also crap so....
Nevertheless good work, congrats.
...
[edit] 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.
Image Image Image
B
42
S
22
G
15
Posts: 372
Reputation: 12,215

Post » 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
91
S
31
G
103
Posts: 5,235
Reputation: 67,756

Post » Thu Sep 25, 2014 7:02 am

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

Thank you!
Image Image Image
B
42
S
22
G
15
Posts: 372
Reputation: 12,215

Post » 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
62
S
14
G
2
Posts: 286
Reputation: 6,576

Post » Thu Apr 27, 2017 5:30 pm

B
91
S
31
G
103
Posts: 5,235
Reputation: 67,756

Next

Return to How do I....?

Who is online

Users browsing this forum: Google [Bot], plinkie and 12 guests