Four-Play with simple AI

Posted by , 27 November 2005 · 26 views

I've applied the classic minimax search to Four-Play, and I'm pleased with the results. The program will anticipate any traps within 7 moves and act accordingly. I was concerned that it might take a long time to search 7 moves ahead, but it turned out not to be too bad.The AI is not terribly difficult to beat at this point because the heuristics are simple. The search just checks whether there is a winning position or not. The next step will be to apply some more sophisticated heuristics, and then the game should be challenging.At the present time, you can only play red, and the Atari plays blue. Have fun!

attachment

Attached Files

fourplay_nov26.bin (4K)
downloads: 81

supercat
Nov 28 2005 1:27 AM

Pretty nice. How are you doing the four-in-a-row checks? And how many cycles per 'loop' does your AI take?

Keeping vertical sync while 'thinking' is nice if you can manage it? Z26 shows 265 lines during the thought process. If you're kinda sorta keeping vertical sync (but off by a few lines) it might be nice to also show a 'thinking' message or progress indication. Don't want to do anything that would take too much CPU time of course, but something quick might be nice.

Report

Zach
Nov 29 2005 7:11 AM

supercat, on Mon Nov 28, 2005 2:27 AM, said:

The method for checking for 4 in a row is straightforward. A 49 byte block of RAM represents the board with one byte for each cell. Every time a new piece falls in, the computer scans the row, column, and two diagonal lines that intersect the piece's position. Of course it keeps a count of the number of pieces in a row it finds. Scanning the column is fastest because it only needs to check the 3 pieces immediately underneath.

You're right about the vertical sync. I've seen z26 report 48 and 999 line frames, and the picture jumps badly on my TV. The 265 line frames are not bad; in fact Video Chess displays the same number of lines during its thinking state.

Report

cd-w
Nov 29 2005 7:54 AM

Very impressive work, and it looks like you are still using only around 2K! I assume it will be possible to vary the depth of the search to enable different skill levels? As pointed out previously, the loss of sync while thinking is slightly annoying. If it is not possible to fit everything between screen refreshes, then you could set a timer, and check it periodically during the thinking time to see if the screen needs to be refreshed? I am looking forward to seeing this completed. At this rate you will soon be able to release a minigame cart containing just your puzzle games!

Chris

Report

Thomas Jentzsch
Nov 29 2005 8:31 AM

Plays really good already (lost the first game

)! Some randomness should be added though.

BTW: Why are there 7 rows? The ones I know have only 6.

Report

vdub_bobby
Nov 29 2005 12:51 PM

I'm just no good at this game. Lost my first match, too. Fun, though, and nicely done.

Report

Zach
Dec 1 2005 6:08 AM

vdub_bobby, on Tue Nov 29, 2005 1:51 PM, said:

I'm just no good at this game. Lost my first match, too. Fun, though, and nicely done.

Here's a hint. It's impossible to get a horizontal or diagonal win without a piece in the center column.

Report

Zach
Dec 1 2005 6:26 AM

Thomas Jentzsch, on Tue Nov 29, 2005 9:31 AM, said:

BTW: Why are there 7 rows? The ones I know have only 6.

The short answer is, why not? The long answer is I wanted to set up a framework for future games, and more games are played on a 7x7 board than 7x6.

One interesting result is a change in the advantage for red. On a 7x6 board, it has been shown that with perfect play, red can force a win. For 7x7, red can only force a draw. Source. Note that making unbeatable AI is beyond the scope of the project.