Connect 4 Minimax

This is a discussion on Connect 4 Minimax within the C++ Programming forums, part of the General Programming Boards category; Hi, Trying to understand the minimax algorithm for a connect 4 game: http://ai-depot.com/articles/minimax-explained/ Would you create a tree for each ...

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    45

    Connect 4 Minimax

    Hi,

    Trying to understand the minimax algorithm for a connect 4 game:
    http://ai-depot.com/articles/minimax-explained/

    Would you create a tree for each of the columns on the connect 4 board. so a board with 4 columns will have 4 trees created?

    If so, the root will be the selected column?...yes? the second level will be the possible opponent choices...yes? and so on?

    Thanks For your help, im pretty new to all this

    Cheers
    -Alex

  2. #2
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    You will have one tree. The values in the tree wil be a rating of the board. For example, if a particular move will make you lose then the value would be zero. If the move will make you win then the value would be the highest possible. The minimax algorithm picks the route that the computer wants to take by picking trying the moves that will yield the highest state for the computer. It then assumes that the human will pick the move that minimizes the computer's state.
    Don't quote me on that... ...seriously

  3. #3
    Registered User
    Join Date
    Aug 2006
    Posts
    45
    Hi,

    So for simplicity its a computer vs human match. Obviously the algorithm is for a computer move decision. So when the computer has to play its move, is the root of the tree (MAX) the humans last move (a thus current game depth) ?

    -Alex

  4. #4
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    The root is the current state. The branches coming off of it are possible moves and the numbers that you see are the rating of the states that result from each move.
    Don't quote me on that... ...seriously

  5. #5
    Registered User
    Join Date
    Aug 2006
    Posts
    45
    Quote Originally Posted by Brad0407 View Post
    The root is the current state. The branches coming off of it are possible moves and the numbers that you see are the rating of the states that result from each move.
    So in connect 4, each node including the root is an 2D ARRAY ?

    Also its not just the computers moves for every level of the tree..its also the humans possible moves.

    so for a 7 column grid. there is a root node then 7 nodes coming of??.. are these the computers possible move or the humans possible moves?

    Sorry about this.. the algorithm documentation available isn't too beginner friendly

    Cheers
    -Alex

  6. #6
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    The root is a single number. Pretend you are rating the board on a scale from 0 to 10 based on how sure you are that you will win. That rating for the current board is the root. All the following numbers are ratings.
    Don't quote me on that... ...seriously

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Hi there...The only language i know is C .Am 18 years old so now i started to learn.I have to make minimax function for othello(reversi). I have understand the way it works,but i can not make it.Code many times is more helpful than words :-)

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Don't resurrect old threads. Start your own.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Non-blocking connect()?
    By pobri19 in forum Networking/Device Communication
    Replies: 9
    Last Post: 04-22-2009, 03:40 PM
  2. connect() function, strange error
    By Mr_Miguel in forum C Programming
    Replies: 1
    Last Post: 12-12-2006, 05:51 PM
  3. connect timeout
    By X PaYnE X in forum Networking/Device Communication
    Replies: 8
    Last Post: 05-14-2005, 09:30 PM
  4. Client timed-out once on connect(), can never connect() again
    By registering in forum Networking/Device Communication
    Replies: 6
    Last Post: 10-28-2003, 02:46 PM
  5. MySQL Connect from Outside Computer
    By juschillin in forum Windows Programming
    Replies: 0
    Last Post: 09-27-2002, 08:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21