Member Avatar for schlulol

Hi, I've been working on a c++ game of connect 4. It uses a multidimensional array, and I have a function that is capable of checking if someone has won. However, ai is really bugging me. I've tried to do some research on this minimax thing, but I couldn't find anything helpful. If someone could explain how it would work for a game of connect 4 in layman's terms (maybe with psuedocode) or refer me to some websites that will actually help me understand, I would greatly appreciate it.

  • 5 Contributors
  • 4 Replies
  • 330 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by m4ster_r0shi

Dani AI

Generated

Minimax in plain terms: build the game tree of possible moves, alternate levels between a maximizer (the AI) and a minimizer (the opponent), score leaf nodes (win = large positive, loss = large negative, draw = 0, or a heuristic for nonterminal leaves), and propagate those scores back up the tree so the root picks the move that maximizes the worst-case outcome. ’s link points to the standard idea, and found full implementations; the short, practical summary below focuses on what to implement for a C++ Connect 4 using a 2D array.

Core algorithm (conceptual steps): generate legal moves (columns not full). For each move: apply the move (drop piece to lowest empty row), check terminal (win/draw) or depth limit; if terminal return utility, else recurse with switched player and depth-1; then undo the move. At the root choose the column with the best returned score. Use alpha–beta pruning to cut branches and a depth limit or time limit so searches finish in reasonable time. As noted, MIN vs MAX is simple; the implementation details are the common stumbling points.

function minimax(board, depth, alpha, beta, maximizing):
    if depth == 0 or gameOver(board):
        return evaluate(board)
    if maximizing:
        best = -INF
        for col in validMoves(board) in preferredOrder:
            row = makeMove(board, col, MY_PIECE)
            score = minimax(board, depth-1, alpha, beta, false)
            undoMove(board, col, row)
            best = max(best, score)
            alpha = max(alpha, best)
            if beta <= alpha: break
        return best
    else:
        best = +INF
        for col in validMoves(board) in preferredOrder:
            row = makeMove(board, col, OPP_PIECE)
            score = minimax(board, depth-1, alpha, beta, true)
            undoMove(board, col, row)
            best = min(best, score)
            beta = min(beta, best)
            if beta <= alpha: break
        return best

Practical tips and common bugs: implement fast makeMove + undoMove (avoid copying whole board), order moves center-first and prefer immediate wins to help pruning, use iterative deepening + time limit for variable search depth, consider a transposition table (Zobrist hashing) to cache positions, and design an evaluation that counts 4/3/2-in-a-row windows with weights (center column preference). Watch for forgetting to undo moves, wrong row indices, or not flipping the maximizing flag — those cause subtle bugs.

Recommended Answers

All 4 Replies

Member Avatar for VernonDozier

Please use one forum or the other for these types of posts or at least link them so people don't waste time aswering here when it's being answered over.

Member Avatar for WaltP

Not a clue what you don't understand. A MIN and MAX are quite obvious so without knowing what bugs you, we can't very well answer your non-question.

Member Avatar for m4ster_r0shi

I've tried to do some research on this minimax thing, but I couldn't find anything helpful.

How much did you search? I just googled connect four c++ minimax and I found this video on youtube. In the description of that video, I found this link, There, you can see a functional implementation of minimax for connect four, which is as good as pseudocode, followed by a detailed explanation. If this is not enough, the guy has also coded implementations in several other languages (including c++), and you can view the full source code on github. And if you want to test his ai, you can play against it on your browser.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.