Owari with Minimax

board.cpp

#include "board.hpp"
#include <iostream>
#include <string.h>

Board::Board()
{
    whoseTurn='S';
    for(int i=0; i<14; i++)
    {
        if((i+1)%7==0)
            pieces[i]=0;        //set goal cup
        else
            pieces[i]=3;        //set cups
    }
}

Board::Board(const Board* board)
{
    whoseTurn=board->whoseTurn;
    memcpy((void*)pieces, (void*)board->pieces, 14);
}

Board::Board(const Board& board)
{
    whoseTurn=board.whoseTurn;
    memcpy((void*)pieces, (void*)board.pieces, 14);
}

void Board::printBoard() const
{
    std::cout << " ";
    for(int i=12; i>6; i--)
        std::cout << (int)(pieces[i]);
    std::cout << std::endl;
    std::cout << (int)(pieces[13]);
    for(int i=0; i<6; i++)
        std::cout << " ";
    std::cout << (int)(pieces[6]) << std::endl;
    std::cout << " ";
    for(int i=0; i<6; i++)
        std::cout << (int)(pieces[i]);
    std::cout << std::endl;

}

int Board::staticEval() const
{
    int out=0;
    for(int i=0; i<7; i++)
    {                           //sum of souths cups and goal plus negated sum of north's cups goal
        out+=pieces[i];
        out-=pieces[i+7];
    }
    return out;
}

void Board::playAt(const int playAt)
{
    char spread=pieces[playAt];
    char endAt=(spread+playAt)%14;
    pieces[playAt]=0;
    for(int i=0; i<spread; i++)
        pieces[(playAt+i+1)%14]++;
    if(pieces[(int)endAt]==1 &&
       ((whoseTurn=='S' && endAt<6) ||
       (whoseTurn=='N' && endAt<13 && endAt>6)))
    {
        int offset=6;
        if(playAt>6)
            offset+=7;
        pieces[offset]+=pieces[(endAt+12-(endAt%7)*2)%14]; //magic
        pieces[(endAt+12-(endAt%7)*2)%14]=0;
    }
    if(whoseTurn=='S')
        whoseTurn='N';
    else
        whoseTurn='S';
}

void Board::addPoints()
{
    for(int i=0; i<6; i++)
    {
        pieces[6]+=pieces[i];
        pieces[i]=0;
    }
    for(int i=7; i<13; i++)
    {
        pieces[13]+=pieces[i];
        pieces[i]=0;
    }
}

bool Board::checkForWin() const
{
    char sumS=0;
    char sumN=0;
    for(int i=0; i<6; i++)
    {
        sumS+=pieces[i];
        sumN+=pieces[i+7];
    }
    return ((!sumS) || (!sumN));
}

bool Board::isValidPlay(int playAt) const
{
    if(whoseTurn=='S')
        if(playAt>5)
            return 0;
    if(whoseTurn=='N')
        if(playAt<6 || playAt>12)
            return 0;
    return (bool)pieces[playAt];
}

board.hpp

#ifndef BOARD_HPP
#define BOARD_HPP

//	Allister Lindamood - aslindamood@alaska.edu
//  Peter Trinh - pptrinh@alaska.edu
//
//	Homework assignment 3
//	10/21/17
//
//	board.hpp
//	A class that contains an Oware board and various functions to manipulate it
//


struct Board
{
    Board();                                //default and copy constructors
    Board(const Board* board);
    Board(const Board& board);

    void printBoard() const;                //print board to screen
    int staticEval() const;                 //Heuristic function- see source for notes
    void playAt(const int playAt);          //play the seeds in cup specified
    bool checkForWin() const;               //check for and end-game state
    void addPoints();                       //deposit remaining seeds into the appropriate owner's goals for scoring
    bool isValidPlay(int playAt) const;     //check if a given move is valid

    char pieces[14];
    char whoseTurn;
};


#endif // BOARD_HPP

main.cpp

#include <iostream>
#include <vector>
#include "board.hpp"
#include "node.hpp"

//	Allister Lindamood - aslindamood@alaska.edu
//  Peter Trinh - pptrinh@alaska.edu
//
//	Homework assignment 3
//	10/21/17
//
//	main.cpp
//	A test routine for the minimax algorithms found in the node classes to solve Owari games
//

int Node::nodesExpanded=0;
int Node::nodesPruned=0;

int main()
{
    Node node;
    node.state.printBoard();
    int input=-1;
    while(!node.state.checkForWin())
    {
        std::cout << "Enter South's input: ";
        std::cin >> input;
        if(input>=0)
        {
            std::cout << "South plays at cup no. " << input << std::endl;
            node.state.playAt(input);
        }
        else
        {
            node.decide(16);
            std::cout << "AI South plays at cup no. " << (int)node.cupPlayed << std::endl;
            node.state.playAt(node.cupPlayed);
        }
        node.state.printBoard();
        node.decide(15);
        std::cout << "Nodes expanded: " << Node::nodesExpanded << ", nodes pruned: " << Node::nodesPruned << std::endl;
        if(node.state.checkForWin())
            break;
        std::cout << "AI North plays at cup no. " << (int)node.cupPlayed << std::endl;
        node.state.playAt(node.cupPlayed);
        node.state.printBoard();
    }
    std::cout << "Game over!\nFinal score: " << std::endl;
    node.state.addPoints();
    node.state.printBoard();
    return 0;
}

node.cpp

#include "board.hpp"
#include <vector>
#include "node.hpp"

Node::Node(const Node* parent, int playAt)
{
    if(parent)
        state=Board(parent->state);
    else
        state=Board();
    if(playAt>=0)
        state.playAt(playAt);               //update board to new state if necessary
    cupPlayed=playAt;
}

int Node::decide(char maxDepth)
{
    nodesExpanded=0;
    nodesPruned=0;
    children.clear();
    if(state.whoseTurn=='S')               //maximize
        evalMax(maxDepth);
    else                                    //minimize
        evalMin(maxDepth);
    return cupPlayed;
}

char Node::evalMax(char maxDepth, char alpha, char beta)
{
    if(maxDepth==0 || state.checkForWin()) //First, check to see if we can go any deeper, or if this state is an endgame state
        return (char)state.staticEval();             //if so, return the heuristic value of this state.
    for(int i=0; i<6; i++)                  //it's important to note that heuristic values here are not side-specific, that is, a heuristic value that is negative is
    {                                           // beneficial to the North player, whereas a positive is beneficial to south
        if(state.isValidPlay(i))           //step through all moves, making sure each move is valid for the given scenario (can't play on an empty cup!)
        {
            nodesExpanded++;
            children.push_back(Node(this, i));  //Expand node
            char compare=children.back().evalMin(maxDepth-1, alpha, beta);      //recursive (bicursive?) call to expand the tree further
            if(compare>alpha)               //check for better maximin value
            {
                alpha=compare;
                cupPlayed=i;                //set the 'last move' variable to the best option from the branch. When the algorithm completes, the 'last move' variable
            }                                   //will be set to the best option from the uppermost branch;
            if(beta<=alpha)
            {                               //check for better preexisting solutions-
                nodesPruned++;
                return alpha;               //if they exist, stop evaluating this branch and simply return the best number found yet
            }
        }
    }
    return alpha;                           //return the maximum heuristic value for a fully expanded branch
}

char Node::evalMin(char maxDepth, char alpha, char beta) //this is all a mirror of evalMax
{
     if(maxDepth==0 || state.checkForWin())
        return state.staticEval();
    for(int i=7; i<13; i++)
    {
        if(state.isValidPlay(i))
        {
            children.push_back(Node(this, i));
            char compare=children.back().evalMax(maxDepth-1, alpha, beta);
            if(compare<beta)
            {
                beta=compare;
                cupPlayed=i;
            }
            if(beta<=alpha)
                return beta;
        }
    }
    return beta;
}

bool Node::isEndState() const
{
    return state.checkForWin();
}

node.hpp

#ifndef NODE_HPP
#define NODE_HPP

//	Allister Lindamood - aslindamood@alaska.edu
//  Peter Trinh - pptrinh@alaska.edu
//
//	Homework assignment 3
//	10/21/17
//
//	node.hpp
//	A class that contains a node for searching Owari board states and various functions to manipulate it
//

struct Node
{
    Node(const Node* parent=(Node*)0x0, const int playAt=-1);               //default constructor

    int decide(char maxDepth=5);                                            //wrapper function for Minimax algorithm- returns cup to play at based on whose turn it is
    char evalMax(char maxDepth, char alpha=0x80, char beta=0x7F);           //Maximizer node for Minimax algorithm
    char evalMin(char maxDepth, char alpha=0x80, char beta=0x7F);           //Minimizer node for Minimax algorithm
    bool isEndState() const;                                                //Check for game over state

    static int nodesExpanded;
    static int nodesPruned;

    char cupPlayed;
    Board state;
    std::vector<Node> children;
};

#endif // NODE_HPP