Update on 'Connect 4' game project - problems w/ minmax algorithm
I've been working on the GUI portion of my C++ Connect-N game project (previously mentioned here), and have gotten it to would could charitably be called a working state. However, the game AI, not to put it to finely, stinks.
I was wondering if anyone here has more experience in implementing a minmax algorithm, and can offer any advice on how to get it to play a suitably challenging game.
The minmax code is:
Code:
#ifndef __CONNECTN_AI_H__
#define __CONNECTN_AI_H__ 1
#include <vector>
#include "connectnboard.h"
namespace ConnectN {
typedef intmax_t Weight;
typedef uint8_t Depth;
const Weight infinity = INTMAX_MAX, neg_infinity = INTMAX_MIN;
struct Node {
Board board;
Grid_Size column;
Weight weight;
Depth depth;
Node(const Board & b, Grid_Size c, Weight w, Depth d):board(b), column(c),
weight(w), depth(d) {
};
Node(const Node & n);
void operator=(const Node & n);
};
class Solver {
private:
Board & board;
Depth search_depth;
Node negamax(Node node, Depth depth, Weight alpha, Weight beta,
Weight color);
std::vector < Node > enumerate_moves(Node node);
void order_moves(std::vector < Node > &children);
Weight evaluate_move(Node & node);
Weight evaluate_node(Node & node);
Weight weight_column(Grid_Size c);
public:
Solver(Board & b, Depth d);
Grid_Size move();
friend class Board;
};
}
#endif
and
Code:
#include<algorithm>
#include <chrono>
#include <cmath>
#include <random>
#include "connectnboard.h"
#include "connectn_AI.h"
namespace ConnectN {
/**
*
*
*/
Node::Node(const Node & n) {
this->board = n.board;
this->column = n.column;
this->weight = n.weight;
this->depth = n.depth;
}
/**
*
*
*/ void Node::operator=(const Node & n) {
this->board = n.board;
this->column = n.column;
this->weight = n.weight;
this->depth = n.depth;
}
/**
*
*
*/
Solver::Solver(Board & b, Depth d = 3):board(b), search_depth(d) {
}
/**
*
*
*/
Grid_Size Solver::move() {
Node top = { this->board, 0, neg_infinity, this->search_depth };
Node found =
this->negamax(top, this->search_depth, neg_infinity, infinity, 1);
return found.column;
}
/**
*
*
*/
Node Solver::negamax(Node node, Depth depth, Weight alpha, Weight beta,
Weight color) {
if (depth == 0 || board.win() == COMPUTER) {
return (Node {
node.board, node.column, color * node.weight, depth}
);
}
std::vector < Node > children = enumerate_moves(node);
order_moves(children);
Node value = { node.board, node.column, neg_infinity, depth };
for (auto child:children) {
value.column = child.column;
Node recursive_value = negamax(child, depth - 1, -beta, -alpha, -color);
value.weight = std::max(value.weight, -recursive_value.weight);
alpha = std::max(value.weight, alpha);
if (alpha >= beta) {
break;
}
}
return value;
}
/**
*
*
*/
std::vector < Node > Solver::enumerate_moves(Node node) {
std::vector < Node > children;
for (Grid_Size i = 0; i < node.board.size(); i++) {
Node child = { node.board, i, 0, static_cast < Depth > (node.depth - 1) };
if (!child.board.add_at(i)) {
continue;
}
if (child.depth != this->search_depth) {
child.board.switch_player();
}
child.weight = evaluate_move(child);
children.push_back(child);
}
return children;
}
/**
*
*
*/
void Solver::order_moves(std::vector < Node > &children) {
std::sort(children.begin(), children.end(),[](Node first, Node second) {
return (first.weight < second.weight);}
);
}
/**
*
*
*/
Weight Solver::evaluate_move(Node & node) {
Grid_Size size = node.board.size();
Weight weight = 0;
Grid_Size column = node.column;
Grid_Size midpoint = std::ceil(size / 2);
// add weight depending on whether the token is on the
// center column(s).
if (size % 2) {
if (node.column == midpoint) {
weight += 4;
}
} else {
// if there are two central columns, weight half as much
// as you would if there is only one
if (column == midpoint - 1 || column == midpoint) {
weight += 2;
}
}
weight += evaluate_node(node);
return weight;
}
/**
* Weight Solver::weight_column(Grid_Size c) -
* @paramc - total number of
*/
Weight Solver::weight_column(Grid_Size c) {
Weight weight = 0;
Grid_Size max = this->board.winning_count;
Grid_Size midpoint = std::floor(max / 2);
if (c >= this->board.winning_count) {
// winning move, weight it the maximum amount
weight = 1000;
} else {
// for every token beyond half the winning amount,
// increase the weighting by 2
Weight weighted_count = c - midpoint;
weight = std::max(0, static_cast < int >(weighted_count + 1)) * 2;
}
return weight;
}
/**
* Weight Solver::evaluate_column(Node& node)
* - scan the neighboring square of a given square to see if there
* is a winning sequence.
* @paramnode - version of board to evaluate
*/
Weight Solver::evaluate_node(Node & node) {
Weight weight = 0;
Player p = node.board.current_player();
Grid_Size size = node.board.size();
Grid_Size offset = node.board.winning_count,
target = static_cast < Grid_Size > (node.board.winning_count - 1),
row = std::max(0, node.board.column_top(node.column) - 1),
column = node.column;
bool check_up = (row < (size - target)),
check_left = (column > offset),
check_right = (column < (size - offset));
if (check_right) {
Grid_Size count = 1;
for (Grid_Size c = column;
c < std::min(size, column + offset)
&& (node.board.grid[row][c] == p); c++, count++) {
// iterate through
}
weight += weight_column(count);
}
if (check_up) {
Grid_Size count = 1;
for (Grid_Size r = row;
(r < std::min(size, row + offset))
&& (node.board.grid[r][column] == p); r++, count++) {
// iterate through
}
weight += weight_column(count);
}
if (check_left) {
Grid_Size count = 1;
for (Grid_Size r = row, c = column, count = 0;
(r < (row + offset)) && (c >= (column - target))
&& (node.board.grid[r][c] == p); r++, c--, count++) {
// iterate through
}
weight += weight_column(count);
}
if (check_right) {
Grid_Size count = 1;
for (Grid_Size r = row, c = column, count = 0;
(r < std::min(size, row + offset))
&& (c < std::min(size, column + offset))
&& (node.board.grid[r][c] == p); r++, c++, count++) {
// iterate through
}
weight += weight_column(count);
}
return weight;
}
}
