For the past few weeks i have been studying AI and this weekend i decided to make a start and develop my own really simple game AI, for the well known game of connect four (http://en.wikipedia....ki/Connect_Four). The game is played on an 8x8 board.

This is my first AI for a two player game (i created an A* pathfinding for a NPC in another project, but that was something totally different).

I decided i want to learn to use the MINIMAX algorithm. The first thing i did, is write a pseudocode solution for it. I posted it below, and i hope anyone would be able to provide me with some hints or tips on whether this code would work or not.

The algorithm is currently very simple and does the following:

- Think 4 moves ahead (2 AI and 2 human moves) and try to prevent human from winning

- No heuristics are used for game states, just -1 for a human win and +1 for an AI win

- No pruning is used, all options are evaluated

Right now, i am not really interested in improving the algorithm (that would be my next step), but i am just curious whether this algorithm will work if i implement it in real (C#) code. I hope somebody would like to read my code and point me to any mistakes, if there are any.

Finally, this is mostly a learning-by-doing thing for me. There will probably be lots of code available online that is much better and can easily solve the problem, but in my opinion the best way for me to learn is to first try and build my own algorithm and only afterwards check what others did better. So any links to complete solutions are not really what i am looking for.

Thank you all for reading!

// MINIMAX AlGORITHM // THINK 4 MOVES AHEAD // // 1. AI move // 2. Human move // 3. AI move // 4. Human move // // Possible different outcomes: // 8*8*8*8 = 4096 (minus earlier finished outcomes) // // Human win gives -1 points // AI win gives +1 points // // ----------- // PSEUDO CODE // ----------- // // create class GAMESTATE with properties: // int(8,8) SQUARES // GAMESTATE Parent // int column // The move made to reach this state // // Create array of class gamestate // states(4,4096) = new GAMESTATE // // ADD current state of board to states (0,0). // // -------------------------------------- // Add all possible states to the array // -------------------------------------- // // for x = 0 to 4 // 4 moves ahead // // for y = 0 to 4096 // check all STATES // // IF states(x,y) != Nothing and states(x,y).winvalue IS NOT 1 or -1 // // for z = 0 to 7 // check all columns // // if column z IS NOT full // PLACE TOKEN in z // ADD STATE TO ARRAY: // states(x+1,y+z) = new GAMESTATE // squares(8,8) = value of squares // with for loops for each square // parent = states(x,y) // column = z // // if wincondition = true // Check whether the new state is a final state (winsituation) // Set winvalue of new state to +1 or -1 // end if // // end if // // next // // end if // next // // next // // ---------------------------------------------------------------- // Check all states from level 4 to 1 and move their values up // ---------------------------------------------------------------- // // // for x is 4 to 1 // Start at the bottom of the tree and work up // // for y is 0 to 4096 // Check all states at this level // // if states(x,y) != nothing // // if x is an even number // Human player (minimizing) is deciding // // if states(x,y).winvalue < states(x,y).parent.winvalue // states(x,y).parent.winvalue = states(x,y).winvalue // end if // // else if x is an odd number // AI player (maximizing) is deciding // // if states(x,y).winvalue > states(x,y).parent.winvalue // states(x,y).parent.winvalue = states(x,y).winvalue // end if // // end if // // next // // next // // ------------------- // Determine AI move // ------------------- // // int BestState = -2 // This integer will be used to record the best option // int MoveColumn // This integer will be used to store the column to get to the best option // // for x is 0 to 8 // Run through all states on level 1 // // if states(1,x).winvalue > BestState // // BestState = states(1,x).winvalue // Update the best option value // MoveColumn = states(1,x).column // Update the column used to get ther // // end if // // next // // return MoveColumn // Let's hope this is actually the best move! //