Author: David Mitchell
Date: 18:18:04 08/26/05
Go up one level in this thread
On August 26, 2005 at 20:28:15, Steve Lim wrote: >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. =) > Two basic idea's can work to unmake a move: 1) Your move has a sqr that it goes to. Just reverse it, and make the destination sqr, empty again. 2) Use TWO ttt boards. One is a temporary holding board. Before you make a move, be sure to save the current board status to the temporary board. Then, when you're ready to unmake the move, just copy the temporary board over to the current board. Either way, you also need to check that your number of moves, and any other flags or indicators that have been changed, are changed back to their earlier status. > >>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. As a programmer, your compiler is "your medium", and takes a lot of work to master all it's particulars. Don't quit though. It's good code ( I didn't write it, btw), and it certainly can be "massaged" to work in Bloodshed, with minor header changes, and etc. You'll be surprised at how well it looks, and of course, the search/eval. I'll send you the exe of it, and get you salivating. :) Dave > >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.