Problem :
When playing a valid move, tree_root->children[col] == NULL, which triggers the second if condition of input_MCTS, and causes the program to immediately terminate, although the move is totally valid.
Cause :
Let's say that we have a LEAF A in the 3th level of the tree. Since A is a leaf, all its children are NULL by default. Now, suppose the user plays the only move that allows the tree to progress towards node A. Before applying that progression, the algorithm launches the branch merging optimization routine. Finally, suppose the unfortunate case where some states are merged into A's children. Then, some of A's children will be non-null (because they've been added following the merge). Therefore, A will no longer be considered as a leaf by the algorithm, and will never be selected for MCTS expansion. But, due to the rules a node must satisfy to be merged, it is guaranteed that at least one child of A has to be NULL. Because A is no longer a leaf, that NULL child will never be created (because it would require A to get selected by the mcts algorithm). Finally, if the game happens to reach that forever-NULL child, input_mcts considers that situation an exception and terminates the program.
Reproducing the bug :
Launch game using : ./out 2000 1
-
User plays 3 (AI plays 3)
At this point, the A leaf as been created in tree_root->3->5
-
User plays 3
This action provokes a merging, and A is now given some children (but none for A->children[5])
(AI plays 5)
At this point, A == tree_root, and A->children[5] == NULL
- User plays 5
This causes the program to crash
Possible solutions :
-
When selecting a node for the mcts algorithm, do not immediately skip NULL children. Instead, try creating a node for it. If it works, accept that new node as a candidate for the next selection iteration. If it fails, then that means the move associated to that node is invalid, so effectively skip it.
-
When trying to merge a branch, if the destination does not already exist or is a leaf, just skip that branch. The current implementation creates the new destination, but this would result in one of its children to be NULL after the merge (and not the others)
-
When trying to elect a NULL node as the new tree_root, rerun a whole MCTS from that position, then elect it. While easy to implement, this solution is not optimal, because it means the (valid) game state associated to the NULL node is always ignored unless it is the current game state (not good if it is a good move that's interessant to investigate early on in the game)
Problem :
When playing a valid move, tree_root->children[col] == NULL, which triggers the second if condition of input_MCTS, and causes the program to immediately terminate, although the move is totally valid.
Cause :
Let's say that we have a LEAF A in the 3th level of the tree. Since A is a leaf, all its children are NULL by default. Now, suppose the user plays the only move that allows the tree to progress towards node A. Before applying that progression, the algorithm launches the branch merging optimization routine. Finally, suppose the unfortunate case where some states are merged into A's children. Then, some of A's children will be non-null (because they've been added following the merge). Therefore, A will no longer be considered as a leaf by the algorithm, and will never be selected for MCTS expansion. But, due to the rules a node must satisfy to be merged, it is guaranteed that at least one child of A has to be NULL. Because A is no longer a leaf, that NULL child will never be created (because it would require A to get selected by the mcts algorithm). Finally, if the game happens to reach that forever-NULL child, input_mcts considers that situation an exception and terminates the program.
Reproducing the bug :
Launch game using :
./out 2000 1User plays 3 (AI plays 3)
At this point, the A leaf as been created in tree_root->3->5
User plays 3
This action provokes a merging, and A is now given some children (but none for A->children[5])
(AI plays 5)
At this point, A == tree_root, and A->children[5] == NULL
This causes the program to crash
Possible solutions :
When selecting a node for the mcts algorithm, do not immediately skip NULL children. Instead, try creating a node for it. If it works, accept that new node as a candidate for the next selection iteration. If it fails, then that means the move associated to that node is invalid, so effectively skip it.
When trying to merge a branch, if the destination does not already exist or is a leaf, just skip that branch. The current implementation creates the new destination, but this would result in one of its children to be NULL after the merge (and not the others)
When trying to elect a NULL node as the new tree_root, rerun a whole MCTS from that position, then elect it. While easy to implement, this solution is not optimal, because it means the (valid) game state associated to the NULL node is always ignored unless it is the current game state (not good if it is a good move that's interessant to investigate early on in the game)