minmax algorithm in C2 (2d array)

0 favourites
  • 12 posts
From the Asset Store
Finding the shortest path through the cells based on the A-star algorithm
  • Hi there,

    has anyone experiences with implementing a minmax algorithm (array-based) for a chess game or can give me some advice?

  • not one?

  • 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.

  • 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.

  • 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

  • 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.

  • 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.

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

    Thank you!

  • R0J0hound can you make the source code public again? thanks

  • Hi R0J0hound,

    thank you again.

    I'll take a look into it and will use it with one of the next projects!

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • R0J0hound thank you for example

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)