Click here to Skip to main content
15,918,617 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
GeneralRe: Drawing Controls Problem Pin
Ravi Bhavnani16-Feb-02 19:19
professionalRavi Bhavnani16-Feb-02 19:19 
GeneralRe: Drawing Controls Problem Pin
John Clump16-Feb-02 19:47
John Clump16-Feb-02 19:47 
GeneralHelp on Designing Tictactoe in VC++ Pin
John Cruz16-Feb-02 15:38
John Cruz16-Feb-02 15:38 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
Shog916-Feb-02 16:18
sitebuilderShog916-Feb-02 16:18 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
alex.barylski16-Feb-02 22:28
alex.barylski16-Feb-02 22:28 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
John Cruz18-Feb-02 12:43
John Cruz18-Feb-02 12:43 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
Christian Graus18-Feb-02 12:47
protectorChristian Graus18-Feb-02 12:47 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
Andrew Peace18-Feb-02 13:09
Andrew Peace18-Feb-02 13:09 
A tic-tac-toe AI alogorithm is quite similar to a Chess AI except much simpler. There are numerous ways to implement it, and recursion is certainly an escellent bet IMHO.

Work around a frameowrk similar to this;

For each player move:
1. Determine possible computer moves
2. For each computer move, guess the player move. Let the computer mentally play the game until a given recursion limit (e.g. 6 moves) is reached.
3. For each series, return a score for that path of play.
4. Collate the data, and the highest scoring move-set wins, and the move is made.

Optimisations can be made, such as after the move tree has been compiled, if the player makes the predicted move, just chop off the inappropriate branches and iterate another level. This is quite a complex optimisation if you are only starting out, but will probably be worthwhile if you want to go that far.

Remember, if the board is empty, and you are playing on a 3x3 grid, there are 3x3 possible moves, i.e. 9 moves. However, once the computer has moved (presuming the computer were to take first play), there will be eight remaining moves for the player. Bearing in mind that the computer will have to guess the player's moves as well as it's own, that means that, if you take to recusion to 6 levels, there are 9P6 possible moves, (i.e. 9x8x7x6x5x4 moves). For a full game, there would be 9! possible moves, i.e. 362,880 possible moves, so you probably wouldn't want to guess out the entire game.

OK - moving away from the actual calculations that have to be done, how would you store this data. If you were to use a tree structure, each node in the tree would need the move data (i.e. X and Y co-ords), a pointer to the next sibling node, a pointer to it's first child node and possible a parent-node pointer. Hence, you would need something like;

class CMoveNode {
public:
   // you'll need to implement proper c'tor and d'tor fns
   CMoveNode() {}
   ~CMoveNode() {}

   BYTE m_XMove;
   BYTE m_YMove;
   CMoveNode *m_pNextSibling;
   CMoveNode *m_pFirstChild;
   CMoveNode *m_pParent;         // do you need this???

private:
   // private members
};
So, all in all a maximum of about (presuming 32-bit pointers), 3*32 + 2*8 = 96 + 16 = 112 bits per node = 14 bytes.

If you were to take the system to 4 levels deep, you'd have as a worst case scenario 9P4 nodes = 3024 nodes, * 14 = ~42K.

Hope that's useful, it's not something I've done before but I've read up on things like this. I don't proclaim to be an expert, but would also be interested to hear yours and others comments on these ideas. Maybe you could do an article when you've finished Big Grin | :-D .

--
Andrew.
GeneralRe: Help on Designing Tictactoe in VC++ Pin
alex.barylski18-Feb-02 14:49
alex.barylski18-Feb-02 14:49 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
John Cruz19-Feb-02 1:19
John Cruz19-Feb-02 1:19 
GeneralRe: Help on Designing Tictactoe in VC++ Pin
Member 139425924-Dec-04 20:17
Member 139425924-Dec-04 20:17 
GeneralMDI - How do I set or activate a view Pin
RobJones16-Feb-02 14:29
RobJones16-Feb-02 14:29 
GeneralRe: MDI - How do I set or activate a view Pin
Derek Waters17-Feb-02 11:35
Derek Waters17-Feb-02 11:35 
GeneralRe: MDI - How do I set or activate a view Pin
RobJones17-Feb-02 12:22
RobJones17-Feb-02 12:22 
GeneralRe: MDI - How do I set or activate a view Pin
Derek Waters17-Feb-02 12:31
Derek Waters17-Feb-02 12:31 
GeneralRe: MDI - How do I set or activate a view Pin
RobJones17-Feb-02 12:38
RobJones17-Feb-02 12:38 
Questionhow to place files in win32 console application project? Pin
padgyx16-Feb-02 13:01
padgyx16-Feb-02 13:01 
AnswerRe: how to place files in win32 console application project? Pin
alex.barylski16-Feb-02 13:36
alex.barylski16-Feb-02 13:36 
QuestionDoubleClick in CComboBox with dropdown-style? Pin
Rybeck16-Feb-02 11:29
Rybeck16-Feb-02 11:29 
AnswerRe: DoubleClick in CComboBox with dropdown-style? Pin
Rybeck17-Feb-02 5:10
Rybeck17-Feb-02 5:10 
GeneralMFC control that works like VB's Image Control Pin
16-Feb-02 10:20
suss16-Feb-02 10:20 
GeneralRe: MFC control that works like VB's Image Control Pin
alex.barylski16-Feb-02 11:30
alex.barylski16-Feb-02 11:30 
GeneralRe: MFC control that works like VB's Image Control Pin
Shog916-Feb-02 14:22
sitebuilderShog916-Feb-02 14:22 
GeneralCFontDialog Pin
16-Feb-02 8:24
suss16-Feb-02 8:24 
GeneralRe: CFontDialog Pin
Joaquín M López Muñoz16-Feb-02 8:39
Joaquín M López Muñoz16-Feb-02 8:39 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.