Author: David Mitchell
Date: 01:23:00 08/26/05
Go up one level in this thread
On August 26, 2005 at 03:29:33, Steve Lim wrote: >Hi All, > >I am trying to understand how to implement a simple minimax search into say a >tictactoe program. Right now, my board is simply a [3][3] array. > >I have writen functions to check for initialize the board, draw the board, check >for wins etc. So now its pretty much ready to referee a 2 player game. > >Where do I begin to implement the recursive minimax in this [3][3] board? How is >the search done? > >Thanks. > >PS. My program was written from the beginning to scale to x by x size board (not >just 3x3 tic tac toe), but I am having trouble detecting a diagonal win on a >large board that doesn't begin in one of the 4 corners. This is a post for Omid and myself, if ever I heard one! :) Omid (author of Falcon), got started in gaming with a minimax tic-tac-toe game, as did I. While Omid wrote his, I was just admiring the beauty of one in a book, and used that as a "study guide" to learn some programming. You should have some functions already in place: MoveGen(), IsLegal(), DisplayMove(), UnMakeMove(), and in my case a big Evalu8(), which handled mini-max, as well. You really don't need mini-max for your program to just referee a game. It needs A/Beta or mini-max to pick the best move, though. To detect a win that doesn't include a corner, you need to scan the board, find each "piece" on the board, and then radiate outward to 12:00, 1:30, 3:00, 4:30, 6:00, 7:30, and 9:00 & 10:30 o'clock, until either you reach a square without a man, a square with an opponent's "piece", or the edge of the board. If you can go three squares without being interrupted by one of these, you have won, of course. I think the key to understanding mini-max & alpha-beta is that FIRST you have to go down into the tree, no scoring, just go down all the way. THEN you begin scoring the positions as you come back UP, so in t-t-t, your depths might be: 1,2,3,4,5,4,5,4,5,4,4,5,4,3,4, etc., as you begin "scouring" the "bottom" of the "pool" of moves. I'll send you the t-t-t game I was fascinated by (it's a little "chewed on" from my messing around, but it works great), it's certainly too much to go into in great detail in a post. You'll need a way to "takeback" a move you're program is "thinking" about because EVERY move get's "proposed" in mini-max. That's about 65,000 moves on the program's first reply, iirc! You'll see it all in the program. It's written in C++. Enjoy, David
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.