Problem 42685. Cody meets Xiangqi: foresee the unseen (Part 2)

Well done!

The problem may be very simple. The computation cost of analytical solution (if it exist) has to be larger than the cost of monte carlo.

I agree, many Cody problems take the opposite route (they force players to find analytical solutions by using very stringent error tolerances or very large numbers/samples) but very few problems favor algorithmic approaches over analytical solutions when both exist (code complexity/cost is perhaps the only evaluation measure that might work this way for some problems; e.g. sum(1:n) vs. n*(n+1)/2). As a problem creator, finding an appropriate evaluation measure is likely the best way to try to "bias" players towards a particular implementation/approach (but imo on of the best things about Cody is the way players will surprise you with unexpected approaches if you let them). Last, just for clarity, this particular solution is not really an analytical solution, and it would still fail to converge for very large Na Nb numbers. It is just a Markov chain reformulation of the problem which simply converges considerably faster than Monte Carlo but it can still be improved in many ways...

Thank you for you guys' constructive comments, which will be taken into account in my future problems.

Thanks for your suggestions. My original purpose was to focus only on Monte Carlo simulations, and thus I intentionally put some checks in EvaluateSolution.p to reject, if possible, any solutions based on analytical expressions only. I understand it is impossible to achieve so for experienced users who might still try to bypass those checks and submit analytical solutions. As you suggested, I will explain explicitly what EvaluateSolution.p is testing and checking. The seed value issue might be due to the imperfection of pseudo random generators. Some specific seed values could generate random numbers which appear to be “more random” with respect to a specific problem. I took advantage of this by selecting a specific “good” seed value so that less trials are required to achieve the specified accuracy (which translates to less running time). If an arbitrary seed value is used (e.g., shuffle), then more trials are needed to achieve the same accuracy. As you commented, I will slightly loosen the tolerance requirement so that only a reasonable amount of trials could achieve the accuracy. Moreover, I will disallow the usage of rng so that similar attempts to taking advantage of the pseudo random number imperfection are avoided. Thanks again for your suggestions.

Thanks for the response!. And yes, disallowing analytical solutions is rather complicated because once players have an exact solution they can very easily compute a random instantiation of those estimates for any arbitrary sample size (e.g. using binomial distribution properties), which should be impossible to tell apart from actual Monte Carlo simulation results, so I really do not see a good way to effectively disallow those types of solutions. The "good seed" approach has the problem that it will only work for a very specific form of Monte Carlo simulation (other perfectly valid ways to generate your random samples would not benefit from the "good seed" selection, so you are effectively disallowing all forms of Monte Carlo simulations except the very specific one that you have in mind). In any way, just my two cents, and thanks for the very interesting problem!

Thanks for the insightful comments. I just updated the problem with a more detailed description of the P-file. Also, I slightly improved the checks in the P-file which should better tell apart (as I hope) analytical solutions from Monte Carlo simulations.