Question MiniMax Algorithm and Foreach skipping Issue

Hi, on line 67 and 132, for some reason I keep gettting this error:

InvalidOperationException: Collection was modified; enumeration operation may not execute.

I feel like all I need to do is move some code around within the coroutines but i'm not sure. The Method PeiceCheckLoop initializes the code and the method GetPossibleMoves Loops by calling it self within the Ienumerator.

Another small issue im having is the Add method on the MiniMaxNode class isn't working, nor is using the add function on the list of nodes.

Edit: One more small note, This is all just logic to collect data about possible move positions and creating the links between the nodes.

Code (CSharp):

1. public class AIManager : MonoBehaviour
2. {
3.     public static AIManager instance;
4.  
5.     public List<PeiceData> myPeices = new List<PeiceData>();
6.     public PeiceData shadowPeice;
7.     public int deepestDepth = 3;
8.     public MiniMaxNode mainNode;
9.     public PeiceData originalSelectedPeice;
10.  
11.     private PeiceMovementManager peiceMovementManager;
12.  
13.     private void Awake()
14.     {
15.         instance = this;
16.     }
17.  
18.     // Start is called before the first frame update
19.     void Start()
20.     {
21.         // Find all peices with Peice Data on the right side of the map.
22.         myPeices.Clear();
23.         myPeices = new List<PeiceData>(TerraceTileManager.instance.tileGroup_Right.gameObject.GetComponentsInChildren<PeiceData>());
24.         peiceMovementManager = PeiceMovementManager.Instance;
25.         PeiceCheckLoop();
26.     }
27.  
28.     public void ResetShadowPeice()
29.     {
30.         shadowPeice.transform.SetParent(null);
31.         shadowPeice.transform.position = Vector3.zero;
32.         shadowPeice.gameObject.SetActive(false);
33.     }
34.     public void PeiceCheckLoop()
35.     {
36.  
37.         // Initializing Main Node
38.         mainNode = new MiniMaxNode();
39.         mainNode.layerID = 0;
40.  
41.         // Clearing preview Data
42.         peiceMovementManager.possibleMovePositions.Clear();
43.  
44.         // Cycling through all peices
45.         foreach (PeiceData peice in myPeices)
46.         {
47.             peice.SelectPeice();
48.  
49.             //Creating new Node
50.             MiniMaxNode node = new();
51.             node.layerID = 1;
52.             mainNode.AddNode(node);
53.  
54.             //Saving main Peice
55.             originalSelectedPeice = peice;
56.  
57.             //TODO: Ghost a peice in each temp position to create more possible positions <= Do this for the depth amount of times
58.             //peiceMovementManager.FindAllPossibleMoves();
59.             StartCoroutine(waitForMoves(node));
60.         }
61.  
62.         Debug.Log("Task Completed...");
63.     }
64.     public IEnumerator waitForMoves(MiniMaxNode PeiceNode)
65.     {
66.         yield return new WaitUntil(() => !peiceMovementManager.generatingMoves);
67.         foreach (MapData move in peiceMovementManager.possibleMovePositions)
68.         {
69.             //yield return new WaitUntil(() => !peiceMovementManager.generatingMoves);
70.             pastDepth = deepestDepth;
71.             GetPossibleMoves(move, deepestDepth, PeiceNode);
72.         }
73.      
74.     }
75.  
76.  
77.     int itteration = 0;
78.     int pastDepth = 0;
79.     //     ~This is where individual checks on the move positions are performed~
80.     public void GetPossibleMoves(MapData mapData, int depth, MiniMaxNode currentNode)
81.     {
82.         //      ~Break Check~
83.         // Break out of loop
84.         if(depth == 0)
85.         {
86.             ResetShadowPeice();
87.             if (mapData.mapTileData.unitPosition.childCount < 0)
88.             {
89.                 PeiceData obj = Instantiate(shadowPeice, mapData.mapTileData.unitPosition);
90.                 obj.transform.position = Vector3.zero;
91.                 obj.gameObject.SetActive(true);
92.             }
93.             return;
94.         };
95.  
96.         //     ~Setup Minimax Node~
97.         // Create Minimax node, setup: LayerID and UnitPositions
98.         MiniMaxNode node = new MiniMaxNode();
99.         node.layerID = (deepestDepth - depth) + 2;
100.         node.unitPosition = mapData.mapTileData.unitPosition;
101.         // add to current node list
102.         currentNode.AddNode(node);
103.  
104.         if (pastDepth != depth)
105.         {
106.             pastDepth = depth;
107.         }
108.  
109.         //     ~Simulating/Ghosting Peice~
110.         // Simulate Peice
111.         GhostPeice(mapData.mapTileData.unitPosition, originalSelectedPeice.GetSize());
112.         // Select Peice
113.         shadowPeice.SelectPeice();
114.         // Wait for moves to Generate
115.      
116.      
117.  
118.         //     ~ Debugging ~
119.         itteration++;
120.         Debug.Log(originalSelectedPeice.name + " Itteration: " + itteration + " At depth: " + depth);
121.  
122.         //    ~Recursive Function Calling~
123.         // Call apon it self
124.         StartCoroutine(waitForGhostMoves(mapData, depth, node));
125.     }
126.  
127.     public IEnumerator waitForGhostMoves(MapData mapData, int depth, MiniMaxNode currentNode)
128.     {
129.         yield return new WaitUntil(() => !peiceMovementManager.generatingMoves);
130.         // Get all possible movess
131.         currentNode.movePositions = peiceMovementManager.possibleMovePositions;
132.         foreach (MapData move in peiceMovementManager.possibleMovePositions)
133.         {
134.             GetPossibleMoves(mapData, depth - 1, currentNode);
135.         }
136.  
137.     }
138.  
139.     public void GhostPeice(Transform unitPosition, Size size)
140.     {
141.         shadowPeice.transform.SetParent(unitPosition);
142.         shadowPeice.transform.position = Vector3.zero;
143.     }
144. }
145.  
146. public class MiniMaxNode
147. {
148.     public int layerID = 0;
149.     public int evaluation = 0;
150.     public int alpha = -1000;
151.     public int beta = 1000;
152.     public List<MapData> movePositions;
153.     public List<MiniMaxNode> nodes;
154.     public Transform unitPosition;
155.  
156.     public MiniMaxNode()
157.     {
158.         movePositions = new List<MapData>();
159.         nodes = new List<MiniMaxNode>();
160.     }
161.  
162.     public void AddNode(MiniMaxNode node)
163.     {
164.         nodes.Add(node);
165.     }
166. }

 

Sorry but you got to declusterfuck this on your own. I suggest starting over. This time dont start Coroutine in Coroutines.

 

Essentially what i'm trying to do is predict possible movements so i can later take those movements, rate them, and use them for the Minimax Algorithm. My issue here is im trying collect all the moves but foreach move I have to create a ghost peice that can take that movements place and then figure out what spaces are available next. Its basically a 3D checkers game I have a system to preview moves and a system to select those previews, and I'm utilizing those. The depth of this search says how far it will predict.

Edit: just keeping my fingers crossed someone has experience with the MiniMax algorithm.

 

Let's not slap brand new labels on things. If you're iterating a collection to find the largest or smallest, there's probably ten million tutorials on how to do that. That's just basic C#.

The above error can be fixed in two ways:

- don't modify the collection while you enumerate it; modify another collection and then at the end, go back and apply your changes in a second pass over the temporary collection, applying changes back to the first.

OR:

- make a copy of the collection initially, then iterate that copy while modifying the original. This can trivially be done with a List<T>() collection by iterating the .ToArray() method instead of the List itself, which makes a transient "snapshot" copy for you.

Whatever is happening here, you must find a way to get the information you need in order to reason about what the problem is.

What is often happening in these cases is one of the following:

- the code you think is executing is not actually executing at all
- the code is executing far EARLIER or LATER than you think
- the code is executing far LESS OFTEN than you think
- the code is executing far MORE OFTEN than you think
- the code is executing on another GameObject than you think it is
- you're getting an error or warning and you haven't noticed it in the console window

To help gain more insight into your problem, I recommend liberally sprinkling Debug.Log() statements through your code to display information in realtime.

Doing this should help you answer these types of questions:

- is this code even running? which parts are running? how often does it run? what order does it run in?
- what are the values of the variables involved? Are they initialized? Are the values reasonable?
- are you meeting ALL the requirements to receive callbacks such as triggers / colliders (review the documentation)

Knowing this information will help you reason about the behavior you are seeing.

If your problem would benefit from in-scene or in-game visualization, Debug.DrawRay() or Debug.DrawLine() can help you visualize things like rays (used in raycasting) or distances.

You can also call Debug.Break() to pause the Editor when certain interesting pieces of code run, and then study the scene manually, looking for all the parts, where they are, what scripts are on them, etc.

You can also call GameObject.CreatePrimitive() to emplace debug-marker-ish objects in the scene at runtime.

You could also just display various important quantities in UI Text elements to watch them change as you play the game.

If you are running a mobile device you can also view the console output. Google for how on your particular mobile target, such as this answer or iOS: https://forum.unity.com/threads/how-to-capturing-device-logs-on-ios.529920/ or this answer for Android: https://forum.unity.com/threads/how-to-capturing-device-logs-on-android.528680/

Another useful approach is to temporarily strip out everything besides what is necessary to prove your issue. This can simplify and isolate compounding effects of other items in your scene or prefab.

Here's an example of putting in a laser-focused Debug.Log() and how that can save you a TON of time wallowing around speculating what might be going wrong:

https://forum.unity.com/threads/coroutine-missing-hint-and-error.1103197/#post-7100494

 

Another way to fix the "can't change list in foreach" is to use a regular for loop, or a while loop. A foreach gives you that error for safety; whereas a for or while is more flexible. But using them takes some thought.

For example, suppose you sometimes want to add after the current node. An easy way is to go backwards through the list. To see how it works, suppose you're on node 56 and want to add. You add node 57, the list gets longer, but the loop just goes i=i-1 and is perfectly on node 55 for the next step. It never incorrectly lands on the node you just added. Deleting also works pretty well going backwards. Or you can go forwards and play with the loop variable more.

But deleting and adding to a big list is slow. It's faster to use a linked list. But then you need to hand-make an iterator for use a normal for or while loop. Not too hard, but not super easy either.

 

Well, to be fair he didn't really invent a new name. Minimax is a well known algorithm for AI for minimizing the loss in the worse case scenario. This computerphile video explains the basic concept quite well.

About the actual problem: We can't really tell what may go wrong since the offending list (possibleMovePositions) seems to live in a different class / script (PeiceMovementManager). As others have already pointed out, whever you're iterating through a foreach loop, you must not change the collection that is iterated over. So you must not add or remove elements inside that loop.

It's next to impossible to make any sense of the code you posted as there is too much missing / hidden code there. However we can see several potential issues in your overall design. For example your foreach loop in like 45 as this line:

Code (CSharp):

1. originalSelectedPeice = peice;

. However you start a new coroutine for each piece. So each iteration would overwrite the value of the originalSelectedPeice variable. So since your "waitForMoves" coroutine would wait for at least one frame, it means only the last element of your list would end up in the "originalSelectedPeice" variable before any of the started coroutines would get to ta point where they actually use that value. So I suspect several major design flaws in that code.

Starting coroutines is quite expensive. Nesting those does not really improve things. It's also bad design to have a list declared in another class and have multiple classes mess with that data. Your AIManager does actually clear the list stored in the "PeiceMovementManager". A manager should be responsible for his own data.

 

I actually just got everything working with async and await with unityasync then i changed all but the foreach statement I used for the peices to for loops. Really appreciate all the help! I have a day till this projects milestone is due and i gotta finish up the AI.