Repository navigation
Expand file tree
/
Copy pathposition.h
More file actions
271 lines (227 loc) · 8.67 KB
/
Copy pathposition.h
File metadata and controls
271 lines (227 loc) · 8.67 KB
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
// Copyright 2018 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef CC_POSITION_H_
#define CC_POSITION_H_
#include <array>
#include <cstdint>
#include <memory>
#include <string>
#include "cc/color.h"
#include "cc/constants.h"
#include "cc/coord.h"
#include "cc/group.h"
#include "cc/inline_vector.h"
#include "cc/logging.h"
#include "cc/stone.h"
#include "cc/zobrist.h"
namespace minigo {
extern const std::array<inline_vector<Coord, 4>, kN * kN> kNeighborCoords;
// BoardVisitor visits points on the board only once.
// A simple example that visits all points on the board only once:
// BoardVisitor bv;
// bv.Begin()
// bv.Visit(0);
// while (!bv.Done()) {
// Coord coord = bv.Next();
// std::cout << "Visiting " << coord << "\n";
// for (auto neighbor_coord : GetNeighbors(coord)) {
// bv.Visit(neighbor_coord);
// }
// }
//
// Points are visited in the order that they are passed to Visit for the first
// time.
class BoardVisitor {
public:
BoardVisitor() = default;
// Starts a new visit around the board.
void Begin() {
MG_DCHECK(Done());
if (++epoch_ == 0) {
memset(visited_.data(), 0, sizeof(visited_));
epoch_ = 1;
}
}
// Returns true when there are no more points to visit.
bool Done() const { return stack_.empty(); }
// Returns the coordinates of the next point in the queue to visit.
Coord Next() {
auto c = stack_.back();
stack_.pop_back();
return c;
}
// If this is the first time Visit has been passed coordinate c since the most
// recent call to Begin, Visit pushes the coordinate onto its queue of points
// to visit and returns true. Otherwise, Visit returns false.
bool Visit(Coord c) {
if (visited_[c] != epoch_) {
visited_[c] = epoch_;
stack_.push_back(c);
return true;
}
return false;
}
private:
inline_vector<Coord, kN * kN> stack_;
std::array<uint8_t, kN * kN> visited_;
// Initializing to 0xff means the visited_ array will get initialized on the
// first call to Begin().
uint8_t epoch_ = 0xff;
};
// GroupVisitor simply keeps track of which groups have been visited since the
// most recent call to Begin. Unlike BoardVisitor, it does not keep a pending
// queue of groups to visit.
class GroupVisitor {
public:
GroupVisitor() = default;
void Begin() {
if (++epoch_ == 0) {
memset(visited_.data(), 0, sizeof(visited_));
epoch_ = 1;
}
}
bool Visit(GroupId id) {
if (visited_[id] != epoch_) {
visited_[id] = epoch_;
return true;
}
return false;
}
private:
std::array<uint8_t, Group::kMaxNumGroups> visited_;
// Initializing to 0xff means the visited_ array will get initialized on the
// first call to Begin().
uint8_t epoch_ = 0xff;
};
// Position represents a single board position.
// It tracks the stones on the board and their groups, and contains the logic
// for removing groups with no remaining liberties and merging neighboring
// groups of the same color.
//
// Since the MCTS code makes a copy of the board position for each expanded
// node in the tree, we aim to keep the data structures as compact as possible.
// This is in tension with our other aim of avoiding heap allocations where
// possible, which means we have to preallocate some pools of memory. In
// particular, the BoardVisitor and GroupVisitor classes that Position uses to
// update its internal state are relatively large compared to the board size
// (even though we're only talking a couple of kB in total. Consequently, the
// caller of the Position code must pass pointers to previously allocated
// instances of BoardVisitor and GroupVisitor. These can then be reused by all
// instances of the Position class.
class Position {
public:
// Interface used to enforce positional superko based on the Zobrist hash of
// a position.
class ZobristHistory {
public:
virtual bool HasPositionBeenPlayedBefore(
zobrist::Hash stone_hash) const = 0;
};
// Initializes an empty board.
// All moves are considered legal.
Position(BoardVisitor* bv, GroupVisitor* gv, Color to_play);
// Copies the position's state from another instance, while preserving the
// BoardVisitor and GroupVisitor it was constructed with.
Position(BoardVisitor* bv, GroupVisitor* gv, const Position& other);
Position(const Position&) = default;
Position& operator=(const Position&) = default;
using Stones = std::array<Stone, kN * kN>;
// Plays the given move and updates which moves are legal.
// If zobrist_history is non-null, move legality considers positional superko.
// If zobrist_history is null, positional superko is not considered when
// updating the legal moves, only ko.
void PlayMove(Coord c, Color color = Color::kEmpty,
ZobristHistory* zobrist_history = nullptr);
const std::array<int, 2>& num_captures() const { return num_captures_; }
// Calculates the score from B perspective. If W is winning, score is
// negative.
float CalculateScore(float komi);
// Returns true if playing this move is legal.
// Does not check positional superko.
// legal_move(c) can be used to check for positional superko.
enum class MoveType {
// The position is illegal:
// - a stone is already at that position.
// - the move is ko.
// - the move is suicidal.
kIllegal,
// The move will not capture an opponent's group.
// The move is not necessarily legal because of superko.
kNoCapture,
// The move will capture an opponent's group.
// The move is not necessarily legal because of superko.
kCapture,
};
MoveType ClassifyMove(Coord c) const;
std::string ToSimpleString() const;
std::string ToPrettyString(bool use_ansi_colors = true) const;
Color to_play() const { return to_play_; }
const Stones& stones() const { return stones_; }
int n() const { return n_; }
zobrist::Hash stone_hash() const { return stone_hash_; }
bool legal_move(Coord c) const {
MG_DCHECK(c < kNumMoves);
return legal_moves_[c];
}
// The following methods are protected to enable direct testing by unit tests.
protected:
// Returns the Group of the stone at the given coordinate. Used for testing.
Group GroupAt(Coord c) const {
auto s = stones_[c];
return s.empty() ? Group() : groups_[s.group_id()];
}
// Returns color C if the position at idx is empty and surrounded on all
// sides by stones of color C.
// Returns Color::kEmpty otherwise.
Color IsKoish(Coord c) const;
// Adds the stone to the board.
// Removes newly surrounded opponent groups.
// DOES NOT update legal_moves_: callers of AddStoneToBoard must explicitly
// call UpdateLegalMoves afterwards (this is because UpdateLegalMoves uses
// AddStoneToBoard internally).
// Updates liberty counts of remaining groups.
// Updates num_captures_.
// If the move captures a single stone, sets ko_ to the coordinate of that
// stone. Sets ko_ to kInvalid otherwise.
void AddStoneToBoard(Coord c, Color color);
// Updates legal_moves_.
// If zobrist_history is non-null, this takes into account positional superko.
void UpdateLegalMoves(ZobristHistory* zobrist_history);
private:
// Removes the group with a stone at the given coordinate from the board,
// updating the liberty counts of neighboring groups.
void RemoveGroup(Coord c);
// Merge neighboring groups of the same color as the stone at coordinate c
// into that stone's group. Called when a stone is placed on the board that
// has two or more distinct neighboring groups of the same color.
void MergeGroup(Coord c);
// Returns true if the point at coordinate c neighbors the given group.
bool HasNeighboringGroup(Coord c, GroupId group_id) const;
Stones stones_;
BoardVisitor* board_visitor_;
GroupVisitor* group_visitor_;
GroupPool groups_;
Color to_play_;
Coord ko_ = Coord::kInvalid;
// Number of captures for (B, W).
std::array<int, 2> num_captures_{{0, 0}};
int n_ = 0;
std::array<bool, kNumMoves> legal_moves_;
// Zobrist hash of the stones. It can be used for positional superko.
// This has does not include number of consecutive passes or ko, so should not
// be used for caching inferences.
zobrist::Hash stone_hash_ = 0;
};
} // namespace minigo
#endif // CC_POSITION_H_