C Four, miGame, Part 5

So I was getting a bit frustrated at this AI, I made that I could beat every time... Had a look online at the solution Wikipedia was talking about. This. Shat my pants looking at the amount of information this things goes through. Some guy actually spend 40,000 hours calculating all the possible positions on the board and creating a txt file that holds all these and the transitions between them.

This is tl;dr.

4,531,985,219,092 different possible combinations of moves. That's quite a lot.

So this project seems to be a bit beyond what I was looking to do... I have a pretty average working AI now though. Wont release it just yet though. [Stop timer 201105061934]. Might work on this again later.

Random unrelated image:

I got a job making a website, which is great for University as I need work hours to graduate, but terrible for the guy who hired me because I have NO experience in html or css or php. Should be fun. Will have a play with this blogs design as well. I do quite like it how it is though. We will see.

Will end up something like this:

C Four, miGame, Part 4

Problem Encountered!!!

Something is wrong with the way I am calculating the 'best move'. My plan was to have every winning option score a number of points equal to the number of free spaces on the board.

So let's say it finds a spot where it can win with 3 empty spaces on the board. This spot has a score of 3. In reality the numbers end up much much larger due to the recursion as it finds multiple winning options from the same initial move.

I tried to have an opponent winning make a negative score, as in you don't want to go there. But this ended up with the effect of 'the opponent can win here so I better not block his win'. Stupid...

Tried changing this to increasing the number but then that doesn't work as well as I had hoped either.

Going to get rid of the how many spaces left option and instead will take into account the number of recursive calls to get to this point. I think I'm going to try put the negative thing back in and then have it decide which to choose based on the number furthest from zero (absolute value).

Also had some trouble with stack overflows so have had to limit the number of recursions. At the moment 7 steps in seems enough. Bear in mind that for every step it create another 7 boards. So this gets quite big quite fast.

tl:dr: I have no idea what I am doing at this point and am trying random things until I get something about right.

C Four, miGame, Part 2

I've noticed a lot of searches hitting my blog with my C Four program I made, here. So I'm going to go into a bit of depth about the game now. A lot of the searches say 'Program that proves Connect 4 is a draw'. This got me curious.

Wikipedia says "The game was solved mathematically by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988). With perfect play, the first player can force a win by starting in the middle column. By starting in the two adjacent columns, the first player allows the second player to reach a draw; by starting with the four outer columns, the first player allows the second player to force a win."
It also has a couple links to freeware you can download that plays the perfect game. But I'd rather solve it myself.

Lulz

Initial thoughts: So we know the concept, get four in a row either diagonally, horizontally or vertically. The board is 7 long and 6 high. This means that we must use the middle column to get a diagonal or horizontal win. Also a diagonal or vertical win needs the two middle rows. As the board is filled row by row, it become immediately clear that middle board dominance is essential.

More lulz

Could do: I know how to model turn based games on a graph with nodes representing game state and then use logic to determine from what states a player can force a win. But that's boring and very time consuming to do by hand. See xkcd has done this for tic-tac-toe.

Will do: So what I'm going to do instead is alter my old version of C Four (get it? Connect Four but it's written in C so I called it C Four...) and create an AI that uses a depth first recursive search to find the optimum position for the next piece. I could have it build a graph at run time and then traverse the graph with each move made but computers are fast enough to handle what I'm trying to achieve here.
Basic: Make a program that looks at every possible move and picks the best one. 


What I will need:
Time. I'm back from University holidays and my memory is terrible so will have to go back and learn C.
Visual Studio or something similar to develop in. I'm posting at work so will download this to my flash drive and play with the idea from there.
Money. Not for this project but it's always good to have money, am I right?

Even more lulz

Akin to my original C Four program the game is going to be in ASCII. If I am able I will keep C Four as it is and simply add the option to verse a computer player or even watch a computer player verse another computer player. This is where the money is at.

[Connect Flour image. Sorry I lost this one. But it is funny]

If it works correctly we should see the two computer players play the exact same game every time. And hopefully player 1 will always win. That would be pretty cool.

I'm going back into hospital tomorrow for my kidney stones again, but workload from University has lessened so will work on it in my downtime.

Cheers,