Author: Steve Lim
Date: 17:28:15 08/26/05
Go up one level in this thread
On August 26, 2005 at 04:23:00, David Mitchell wrote: >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. > I think for TicTacToe, MoveGen() (putting pieces into the array is simple(?). If I understand correctly, I have MoveGen(), IsLegal(), DisplayMove() all done. I have read about UnMakeMove() before.. this is where I lose my mind. I do _not_ have that implemented and have no idea where to begin. heh. =) >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. Exactly. Right now, my program has all the other function in place. I'm ready for the 'Engine' as it were. =) >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. Makes sense! I will use this to implement non-square boards in a future version of x in a row type game. >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 Thanks for your time David. Alas, My compiler (BloodShed's Dev C++) cannot compile your code. Argh. Cheers, Steve.
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.