Choose new actions at random when expanding, reducing the bias from t…

…he move order of the legal moves. PiperOrigin-RevId: 305842642 Change-Id: Id47c420f7d71e08da51e12479686e97806008260
anana10c · Apr 14, 2020 · 233004d · 233004d
1 parent fe818a6
commit 233004d
Show file tree

Hide file tree

Showing 2 changed files with 15 additions and 16 deletions.
diff --git a/open_spiel/algorithms/is_mcts.cc b/open_spiel/algorithms/is_mcts.cc
@@ -295,23 +295,22 @@ Action ISMCTSBot::SelectActionUCB(ISMCTSNode* node) {
 }
 
 Action ISMCTSBot::CheckExpand(ISMCTSNode* node,
-                              const std::vector<Action>& legal_actions) const {
-  if (!allow_inconsistent_action_sets_) {
-    // Faster use case for the default setting.
-    if (node->child_info.size() < legal_actions.size()) {
-      return legal_actions[node->child_info.size()];
-    } else {
-      return kInvalidAction;
-    }
-  } else {
-    // Search for the first action not in the child info.
-    for (Action action : legal_actions) {
-      if (node->child_info.find(action) == node->child_info.end()) {
-        return action;
-      }
-    }
+                              const std::vector<Action>& legal_actions) {
+  // Fast check in the common/default case.
+  if (!allow_inconsistent_action_sets_ &&
+      node->child_info.size() == legal_actions.size()) {
     return kInvalidAction;
   }
+
+  // Shuffle the legal actions to remove the bias from the move order.
+  std::vector<Action> legal_actions_copy = legal_actions;
+  std::shuffle(legal_actions_copy.begin(), legal_actions_copy.end(), rng_);
+  for (Action action : legal_actions_copy) {
+    if (node->child_info.find(action) == node->child_info.end()) {
+      return action;
+    }
+  }
+  return kInvalidAction;
 }
 
 std::vector<double> ISMCTSBot::RunSimulation(State* state) {

diff --git a/open_spiel/algorithms/is_mcts.h b/open_spiel/algorithms/is_mcts.h
@@ -108,7 +108,7 @@ class ISMCTSBot : public Bot {
   // actions). If so, returns an action not yet in the children. Otherwise,
   // returns kInvalidAction.
   Action CheckExpand(ISMCTSNode* node,
-                     const std::vector<Action>& legal_actions) const;
+                     const std::vector<Action>& legal_actions);
 
   // Returns a copy of the node with any actions not in specified legal actions
   // removed.