実現したいこと
UNOにおけるモンテカルロ木探索を実装したいと考えている．
発生している問題・分からないこと
130ゲーム目前後でエラーを吐く．恐らくメモリ不足だと思われるが私の知識が無いためよく分からない．
エラーメッセージ
error
1terminate called after throwing an instance of 'std::bad_alloc'
2 what(): std::bad_alloc
該当のソースコード
C++
1struct Node {
2 int player_num;
3 vector<double> value;
4 vector<vector<double>> process_value;
5 int count;
6 shared_ptr<Node> parent;
7 vector<shared_ptr<Node>> children;
8 bool is_extended;
9 State state;
10 vector<vector<Card>> each_hand;
11 vector<Card> card_set;
12 int depth;
13};
14
15vector<int> playoutMCTS(State &state, vector<Card> &card_set, vector<vector<Card>> &each_hand) {
16 int current_player = state.next_player_num;
17 vector<Card> valid_cards = getValidCards(state.card_play_before, each_hand[current_player]);
18 if (valid_cards.empty()) {
19 drawCards(1, current_player, state, card_set, each_hand);
20 valid_cards = getValidCards(state.card_play_before, each_hand[current_player]);
21 }
22 if (!valid_cards.empty()) {
23 int num = randomByNumber(valid_cards.size());
24 Card play_card = valid_cards[num];
25 state.field_cards.push_back(play_card);
26 state.card_play_before = play_card;
27 removeCard(play_card, each_hand[current_player]);
28 // 記号カードの処理、文字数制限のため省略
29 }
30 passTurn(state);
31 if (each_hand[current_player].empty()) {
32 vector<int> points(4, 0);
33 vector<int> ranks(4, 4);
34 for (int i = 0; i < 4; i++) {
35 points[i] = calcPoints(current_player, i, each_hand);
36 }
37 for (int i = 0; i < 4; i++) {
38 for (int j = 0; j < 4; j++) {
39 if (i == j) continue;
40 if (points[i] >= points[j]) ranks[i]--;
41 }
42 }
43 return ranks;
44 }
45 return playoutMCTS(state, card_set, each_hand);
46}
47
48void extend(shared_ptr<Node> node) {
49 State state;
50 int player_num = node->player_num;
51 vector<Card> valid_cards = getValidCards(node->state.card_play_before, node->each_hand[player_num]);
52 vector<Card> field_cards = node->state.field_cards;
53 vector<Card> card_set = node->card_set;
54 if (valid_cards.empty()) {
55 vector<vector<Card>> each_hand = node->each_hand;
56 state = {node->state.card_play_before, field_cards, node->state.turn_right, node->state.next_player_num};
57 passTurn(state);
58 shared_ptr<Node> child_node = make_shared<Node>(Node{player_num, {0.0, 0.0, 0.0, 0.0}, {{}, {}, {}, {}}, 0, node, {}, false, state, each_hand, card_set,
59 node->depth + 1});
60 node->children.push_back(child_node);
61 } else {
62 for (int i = 0; i < valid_cards.size(); i++) {
63 vector<vector<Card>> each_hand = node->each_hand;
64 removeCard(valid_cards[i], each_hand[player_num]);
65 field_cards.push_back(valid_cards[i]);
66 Card card_play_before = valid_cards[i];
67 state = {card_play_before, field_cards, node->state.turn_right, node->state.next_player_num};
68 // 記号カードの処理、文字数制限のため省略
69 passTurn(state);
70 if (valid_cards[i].special == Special::WILD || valid_cards[i].special == Special::WILD_DRAW_4 || valid_cards[i].special == Special::WILD_SHUFFLE) {
71 for (Color color : ARR_COLOR) {
72 Card card = {color, -1, state.card_play_before.special};
73 state = {card, field_cards, node->state.turn_right, node->state.next_player_num};
74 shared_ptr<Node> child_node = make_shared<Node>(Node{player_num, {0.0, 0.0, 0.0, 0.0}, {{}, {}, {}, {}}, 0, node, {}, false, state, each_hand, card_set, node->depth + 1});
75 node->children.push_back(child_node);
76 }
77 } else {
78 shared_ptr<Node> child_node = make_shared<Node>(Node{player_num, {0.0, 0.0, 0.0, 0.0}, {{}, {}, {}, {}}, 0, node, {}, false, state, each_hand, card_set, node->depth + 1});
79 node->children.push_back(child_node);
80 }
81 }
82 }
83}
84
85int decideByUCBtuned(shared_ptr<Node> p) {
86 vector<double> ucb(p->children.size(), 0);
87 int total_playout = p->count - EXTEND_NUMBER;
88 for (int i = 0; i < p->children.size(); i++) {
89 shared_ptr<Node> child = p->children[i];
90 if (child->count == 0) {
91 ucb[i] = 999999;
92 } else {
93 double ave = child->value[p->player_num] / child->count;
94 double vsum = 0.0;
95 double V = 0.0;
96 for (int j = 0; j < child->process_value[p->player_num].size(); j++) {
97 vsum += pow(ave - child->process_value[p->player_num][j], 2);
98 }
99 V = vsum / child->count + sqrt(2 * log(total_playout) / child->count);
100 if (V >= 0.25) {
101 ucb[i] = ave + sqrt(0.25 * log(total_playout) / child->count);
102 } else {
103 ucb[i] = ave + sqrt(V * log(total_playout) / child->count);
104 }
105 }
106 }
107
108 int max = 0;
109 for (int i = 1; i < ucb.size(); i++) {
110 if (ucb[max] < ucb[i]) max = i;
111 }
112 return max;
113}
114
115void update(shared_ptr<Node> node, vector<int> value) {
116 for (shared_ptr<Node> p = node->parent; p != nullptr; p = p->parent) {
117 p->count += 1;
118 for (int i = 0; i < 4; i++) {
119 p->value[i] += (4.0 / value[i] - 1.0) / 3.0;
120 p->process_value[i].push_back((4.0 / value[i] - 1.0) / 3.0);
121 }
122 }
123}
124
125void startPlayoutMCTS(shared_ptr<Node> node) {
126 shared_ptr<Node> p = node;
127 while (p->is_extended) {
128 int next = decideByUCBtuned(p);
129 p = p->children[next];
130 }
131
132 if (p->count >= EXTEND_NUMBER) {
133 extend(p);
134 p->is_extended = true;
135 int next = decideByUCBtuned(p);
136 p = p->children[next];
137 }
138 vector<int> result = playoutMCTS(node->state, node->card_set, node->each_hand);
139 for (int i = 0; i < 4; i++) {
140 p->value[i] += (4.0 / result[i] - 1.0) / 3.0;
141 p->process_value[i].push_back((4.0 / result[i] - 1.0) / 3.0);
142 }
143 p->count += 1;
144 update(p, result);
145}
146
147Card mcts(State &state, vector<Card> &my_hand, vector<int> &num_of_each_hand) {
148 State new_state;
149 vector<vector<Card>> each_hand(4);
150 vector<Card> card_set;
151 vector<Card> field_cards;
152 vector<Card> valid_cards = getValidCards(state.card_play_before, my_hand);
153 vector<Card> valid_actions;
154 for (Card card : valid_cards) {
155 if (card.special == Special::WILD || card.special == Special::WILD_DRAW_4 || card.special == Special::WILD_SHUFFLE) {
156 for (Color color : ARR_COLOR) {
157 valid_actions.push_back({color, -1, card.special});
158 }
159 } else {
160 valid_actions.push_back(card);
161 }
162 }
163
164 for (Color color : ARR_COLOR) {
165 for (int number : ARR_NUMBER) {
166 Card card = {color, number, Special::NONE};
167 card_set.push_back(card);
168 if (number != 0) {
169 card_set.push_back(card);
170 }
171 }
172 for (Special special : ARR_SPECIAL) {
173 Card card = {color, -1, special};
174 card_set.push_back(card);
175 card_set.push_back(card);
176 }
177 }
178 for (Special special : ARR_WILD) {
179 Card card = {Color::BLACK, -1, special};
180 card_set.push_back(card);
181 if (special != Special::WILD_SHUFFLE) {
182 card_set.push_back(card);
183 card_set.push_back(card);
184 card_set.push_back(card);
185 }
186 }
187 for (Card card : my_hand) {
188 each_hand[0].push_back(card);
189 removeCard(card, card_set);
190 }
191 for (Card card : state.field_cards) {
192 field_cards.push_back(card);
193 removeCard(card, card_set);
194 }
195 for (int i = 1; i < 4; i++) {
196 for (int j = 0; j < num_of_each_hand[i - 1]; j++) {
197 int num = randomByNumber(card_set.size());
198 each_hand[i].push_back(card_set[num]);
199 card_set.erase(card_set.begin() + num);
200 }
201 }
202
203 Card card_play_before = state.card_play_before;
204 new_state = {card_play_before, field_cards, state.turn_right, 0};
205 shared_ptr<Node> node = make_shared<Node>(Node{0, {0.0, 0.0, 0.0, 0.0}, {{}, {}, {}, {}}, EXTEND_NUMBER, nullptr, {}, false, new_state, each_hand, card_set, 0});
206 for (int i = 0; i < PLAYOUT * valid_actions.size(); i++) {
207 startPlayoutMCTS(node);
208 }
209
210 int max = 0;
211 for (int i = 0; i < node->children.size(); i++) {
212 if (node->children[max]->count < node->children[i]->count) {
213 max = i;
214 }
215 }
216 return node->children[max]->state.card_play_before;
217}
試したこと・調べたこと
上記の詳細・結果
Node*からshared_ptr<Node>と変更したことで，エラーを吐くのが4ゲーム目前後から130ゲーム目前後になった．
補足
特になし
Q&A
ベストアンサー
