質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.39%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

222閲覧

terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_allocを解決したい

qwerty_

総合スコア1

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2024/09/11 10:51

編集2024/09/11 11:56

実現したいこと

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}

試したこと・調べたこと

  • teratailやGoogle等で検索した
  • ソースコードを自分なりに変更した
  • 知人に聞いた
  • その他
上記の詳細・結果

Node*からshared_ptr<Node>と変更したことで,エラーを吐くのが4ゲーム目前後から130ゲーム目前後になった.

補足

特になし

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

qwerty_

2024/09/11 11:00 編集

省略した記号カードの処理は以下の通りです. switch (play_card.special) { case Special::SKIP: passTurn(state); break; case Special::REVERSE: state.turn_right = !state.turn_right; break; case Special::DRAW_2: passTurn(state); drawCards(2, state.next_player_num, state, card_set, each_hand); break; case Special::WILD: case Special::WILD_DRAW_4: case Special::WILD_SHUFFLE: state.card_play_before.color = ARR_COLOR[randomByNumber(ARR_COLOR.size())]; if (play_card.special == Special::WILD_DRAW_4) { passTurn(state); drawCards(4, state.next_player_num, state, card_set, each_hand); } else if (play_card.special == Special::WILD_SHUFFLE) { shuffleCards(state, each_hand); } break; default: break; }
guest

回答1

0

ベストアンサー

全体のコードを見てないので当てずっぽうですが、

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;

parentshared_ptr<Node> から Node* にすると解決するかもしれません。

循環参照ができているため、手動でNode間の接続を切らない限りツリー全体がデストラクトされない気がします。

投稿2024/09/11 12:39

int32_t

総合スコア21525

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

qwerty_

2024/09/12 07:53

回答ありがとうございます。 試したところ問題が解決しました! ベストアンサーに選ばせていただきました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.39%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問