Does Monte Carlo Tree Search not work on games without the same initial state?
If the initial state is not always the same, but if your agent is allowed to observe what the initial state is before it has to start running the search algorithm, there's basically no problem; it has all the information it needs when it starts running the tree search. This is how we typically use MCTS (or any other tree searches): we first observe what the current state looks like, and then start running the tree search for this state.
If for whatever reason you already have to start running your tree search without being allowed to observe which initial state has been randomly drawn, you can easily just pretend that you actually do have a &quot;dummy&quot;, deterministic initial state which you can observe right before the real initial state, and pretend that the random sampling of an initial state is actually a random event / random transition resulting from a &quot;dummy action&quot;. Then you can handle this scenario in exactly the same way that you would any normal game that has non-deterministic transitions (such as games that involve dice): if you have access to explicit knowledge of which stochastic events are possible, and what their probabilities are, you can encode them as chance nodes. If you do not have such explicit knowledge available, you can use an &quot;open-loop&quot; MCTS. See also: https://ai.stackexchange.com/a/13919/1641

Presence of opponents / other players in the game is a different issue. MCTS and other game tree search algorithms were designed specifically for this, they have no problems handling that. In a tree search, you do not just have nodes for your own agent and the states in which it is allowed to act; you also have nodes for any opponents and any states in which they are allowed to act, and the tree search enables you to reason about what actions your opponents are likely to take.