Problem 42685. Cody meets Xiangqi: foresee the unseen (Part 2)
It seems that the only way to get rid of analytical solutions is to make the problem extremely hard such that nobody manages to derive the analytical solution, or the analytical solution simply does not exist...
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.
Hi Alfonso, Are you suggesting to me that the solution should not depend on rng settings? If that's the case, I need to increase the tolerance values in the test suite such that rng setting needs not be changed manually in one's solution. Any other suggestions from you would be greatly appreciated. Thanks.
I was just trying to figure out what the EvaluateSolution.p code might be doing. Yes, there is some strange behavior where "exact" solutions are not accepted, and sufficiently close random solutions are only accepted for very specific seed values (which would be impossible to guess for players). If possible, I would suggest just to post the actual code in EvaluateSolution or at least explicitly say what it is testing for so players do not have to guess
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.
Problem Recent Solvers5
Make an N-dimensional Multiplication Table
Poker Series 01: isStraightFlush
Matrix which contains the values of an other matrix A at the given locations.
More from this Author29
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!