libneuralnet/ABSearch.cpp at master · spbond/libneuralnet · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*
 * ABSearch.cpp
 *
 *  Created on: Jun 20, 2014
 *      Author: shaun
 */

#include "ABSearch.h"

#include <limits>
using std::numeric_limits;

#include <algorithm>
using std::min;
using std::max;


namespace
{
const float MAX_FLOAT =  numeric_limits<float>::max();
const float MIN_FLOAT = -numeric_limits<float>::max();
}

namespace NN
{

// Constructor
// Pre: nn must be a valid neural net which will evaluate inputs provided by mf
//      mf must provide a vector of all possible moves for the game
//      player1 indicates whether or not the search
//          tree will evaluate the inputs as player 1
// Post: The AB_Search object will evaluate inputs using nn
//       The AB_Search tree will search to a max depth of md
//
AB_Search::AB_Search(shared_ptr<NeuralNet> nn, shared_ptr<MoveFinder> mf,
                     size_t md, bool player1)
: m_neuralnet(nn), m_finder(mf), m_max_depth(md), m_player(player1)
{}

AB_Search::~AB_Search()
{}

// board must have 32 values
// depth is >= 1
float
AB_Search::maximize( const vector<float>& board, float beta, size_t depth )
{
    if( depth < m_max_depth )
    {
        vector<vector<float>> moves = move(m_finder->possibleMoves(board, m_player));
        float alpha = MIN_FLOAT;

        for( auto ii = 0u; ii < moves.size(); ++ii )
        {
            alpha = max( alpha, minimize( moves[ii], alpha, depth + 1) );
            if( alpha >= beta )
            {
                break;
            }
        }

        return alpha;
    }
    else    //terminal node
    {
        return m_neuralnet->evaluate( board );
    }
}

// board must have 32 values
// depth is >= 1
float
AB_Search::minimize( const vector<float>& board, float beta, size_t depth )
{
    if( depth < m_max_depth )
    {
        vector<vector<float>> moves = move(m_finder->possibleMoves(board, !m_player));
        float alpha = MAX_FLOAT;

        for( auto ii = 0u; ii < moves.size(); ++ii )
        {
            alpha = min( alpha, maximize( moves[ii], alpha, depth + 1) );
            if( alpha <= beta )
            {
                break;
            }
        }

        return alpha;
    }
    else    // terminal node
    {
        return m_neuralnet->evaluate( board );
    }
}


vector<float>
AB_Search::nextMove(const vector<float>& current_state)
{
    vector<vector<float>> moves = move(m_finder->possibleMoves(current_state, m_player));
    vector<float> best_move = current_state;
    float alpha = MIN_FLOAT;

    // Find which possible move has the highest guaranteed value
    for( auto ii = 0u; ii < moves.size(); ++ii )
    {
        float value = minimize( moves[ii], alpha, 1 );
        if( value >= alpha )    // If it is better than the previous best, save it
        {
            alpha = value;
            best_move = move(moves[ii]);
        }
    }

    return best_move;
}

vector<float>
AB_Search::nextMove(const vector<float>& current_state, size_t max_depth)
{
    size_t default_depth = m_max_depth;
    m_max_depth = max_depth;

    vector<float> move = nextMove(current_state);

    m_max_depth = default_depth;

    return move;
}

vector<float>
AB_Search::operator ()(const vector<float>& current_state)
{
    return nextMove(current_state);
}

vector<float>
AB_Search::operator ()(const vector<float>& current_state, size_t max_depth)
{
    return nextMove(current_state, max_depth);
}

} /* namespace NN */