Can you beat my Connect4 bot?

[SCM]

What is Minimax and A* searching algorithm?

[na_th_an]

http://www.aihorizon.com/essays/basiccs/...inimax.htm

http://en.wikipedia.org/wiki/A_Star_Search_Algorithm

[wizardlife]

Minimax and A* searching algorithm. That owns and can make your program unbeatable.

Yeah, except that it needs to run on an RCX: 16 MHz and 32k total memory. More like 16k practical once you download the kernel and program.

The way this works is it evaluates the value of the board that each new piece represents by only checking for groups and threats around that, and so creating any number of multiple pieces in a row is 'good', as is blocking the opponent's muliples... but it only counts them if one end of it is 'open', otherwise there's no point.

Agamemnus: Good plan, but I don't have the processor power for that kind of analysis on this platform.

SCM: I know about the 1432 win and it's varients. I thought I had that corrected... perhaps I posted an older version by mistake. The problem before was that it was still creating child nodes off of the win situation... so it considered letting you win worthwhile since that would let itself win the next turn. :roll: I'll check that on the current one and post back.

[Dj Dennie]

You want your connect 4 bot to win every time? Well, you're lucky that somebody managed to figure out a perfect solution to it. This means that the player who goes first can always win...

Have a look: http://www.tomski.com/archive/000092.html

or here's a direct link to the pdf document: http://www.tomski.com/archive/connect4.pdf

[wizardlife]

You want your connect 4 bot to win every time? Well, you're lucky that somebody managed to figure out a perfect solution to it. This means that the player who goes first can always win...

I've looked through Victor Allis's stuff already. It's great for a human player, but completely impractical to try to program. There was only one Javabot that I saw that claimed to be using that system, and source wasn't provided. Anyhow, here's a slightly updated version. Here I'm showing what 'values' the program is establishing for the moves. (of both players)

http://www.angelfire.com/wizard/pigeonca...nect4a.exe

[oracle]

I won on the first try. It's pretty easy, really: just set up a "double cross" and he falls right into it

eg:

Code:

- - - - - - -
- - - - - - -
- - - - - - -
- - o - - - -
- - x o o - -
- - x o o - -
- - o x x o -

(that's a simplified version, but you get the idea).

[SCM]

145443526273
1445463546
444335452 illegal operation
4443535664 illegal operation (top row) I would have been in position to force a win
44435356621 illegal operation (There was a column of 3 X's in the top 3 rows on the previous move).
I think the program is trying to put X's above the top row.

Edit: I started looking at the values you have for each column. Full columns are 0's.

[wizardlife]

145443526273
1445463546
444335452 illegal operation
4443535664 illegal operation (top row) I would have been in position to force a win
44435356621 illegal operation (There was a column of 3 X's in the top 3 rows on the previous move).
I think the program is trying to put X's above the top row.

Edit: I started looking at the values you have for each column. Full columns are 0's.

Yeah, but if every other column is negative, it will still try to put one in the full column. I'll put in a fix for that... the stupid problem with the 6th row is frustrating me, tho, cause if you put one in there it doesn't actually crash until right before your next turn, which means its crashing on the tree expansion stage rather than the actual playing of the move... I think it must be that there's a null (0) pointer to signify the end of that branch and it's trying to expand it anyways and is writing over memory at the null pointer. (a no-no for sure).

Anyhow, thanks for all the help, guys. This algorithm is what I'll show at this event on the weekend, and for the actual competition, I'll work on some pruning so that I have enough memory for a fourth ply so that it can see those traps.

[Agamemnus]

If you have 16K memory, you can prolly use 14K of that for your tree.. if you compress it you'll have maybe 7000 or more possible decisions to evaluate.. 7000 loops... 2 or 3 seconds maybe with 16mhz...

[wizardlife]

If you have 16K memory, you can prolly use 14K of that for your tree.. if you compress it you'll have maybe 7000 or more possible decisions to evaluate.. 7000 loops... 2 or 3 seconds maybe with 16mhz...

What do you mean by 'compress'? I figure each node takes 7 pointers (14 bytes) and one byte that stores the column of the new piece. (plus a byte for the value of the board) I reckon that's about 850 nodes in the tree, which is three turns. My plan is that I'll evaluate three turns ahead, then ditch the three worst options based on the known information and use the freed up memory to make an extra ply on the remaining tree. Something like that, anyways.