[dennybritz]

I think there are some key differences to cycles in Chess. In Chess, the cycles come from your (or your opponents) actions. With minimax you would max (or min) over these actions, so if you pruned away the cycles at some depth your result is not incorrect because the min or max does not change. But here the cycles come from randomness in the game of which chess has none, and you need to take an expectation over the cycles. So you can't just prune them away without changing the result.

A scoring function could definitely help guide the exploration and/or prune the tree, but only at the action nodes, not the environment randomness nodes. Rolling out the full tree more than 1-2 levels would be infeasible because of the randomness in the environment. When you take an action, the randomness can transport you into an exponential number of states, so you have a huge branching factor that is much larger than chess. I think in chess you have a factor of 40ish? Here it's more like ~1000 or ~10,000 depending on the item.

I also wouldn't know how to design a scoring function for this. If you do something simple to take the number of missing modifiers you will end up stuck in bad states. Maybe there is something really clever here that you can do, but I don't know what it is.

If you have an idea how to make tree search work for this I'd love to try it.

[redrobein]

I think the heuristic approach is not as bad as you think. Human crafters, and the current crafting techniques we have are pretty efficient. You don't need to explore the full graph of random states because the mod weights themselves are a representation of those states. As a human I can't think of any crafting item (alt and chaos spamming aside) where the probability isn't a simple to understand number. You think you can use something like modweight x currency cost (x some time modifier for acquisition and use of currency) for scoring. This is how craftofexile does it.

[redrobein]

The more I think about this the more I feel you went really overkill on this. The complexity is several orderers of magnitude lower than what you claim. Like try crafting stuff on the emulator and see how easily you can narrow it down to usually 2 or 3 choices at most steps. There should be really easy heuristics to invalidate most branches. I've also used the COE simulator a ton and never had to model something that's on the order of 50+ states even.

[toolslive]

Just a remark about the cycles not changing the min-max. That's not correct. Identical positions do not always have the same value. Sometimes, a reaching the same position again will allow a player to claim a draw (3 times repetition). Sometimes a repeated position will bring them closer to some other draw mechanism (fe 50 moves without a capture or pawn move).

[toolslive]

However, reading this, It seems like a good fit to try a genetic algorithm. I know, GAs are regarded as a complete backwater in AI these days, but nature has shown that they work in these kind of situations.