This is the second part of the Xiangqi series. The first part in this series is: Cody meets Xiangqi: foresee the unseen (Part 1)
Being increasingly interested in Xiangqi (a.k.a., Chinese Chess), Mr. Cody has designed a new Xiangqi match for Xiang Yu and Liu Bang by taking into account the likelihood of tie games. The new rule is described as follows:
Once
1) Xiang Yu wins Na games consecutively, 2) Liu Bang wins Nb games consecutively, 3) No ties occur consecutively,
whichever comes first, Mr. Cody announces the outcome accordingly as follows:
1) Xiang Yu is the final winner, 2) Liu Bang is the final winner, 3) They end up with a final draw.
Again, Cody asks us --- active Cody players --- to foresee the outcome of this unseen match using Monte Carlo simulations. Our task is to write the following function
[Pa, Pb, Pc] = Xiangqi2(a, b, Na, Nb, Nc)
where
The main focus of this problem is on Monte Carlo simulations, rather than analytical approaches. Your provided solution Xiangqi2.m will be checked by a P-file EvaluateSolution.p, which mainly does 3 things as follows:
1) Call your function [Pa, Pb, Pc] = Xiangqi2(a, b, Na, Nb, Nc) and then Check if the result P = [Pa, Pb, Pc] is within tolerance of its expected value Q. That is, If norm(P - Q) < tol holds, it means that your solution is accurate enough. If this does not hold, your solution will be rejected.
2) Check if your solution is based on pure Monte Carlo simulations or analytical approaches. If it is based on analytical approaches (i.e., using analytical expressions to directly compute the probabilities), then your solution will be rejected. EvaluateSolution.p accomplishes this goal by exploiting a combination of distinct features possessed by analytical solutions, but are generally not shared by Monte Carlo simulations.
3) If your solution passes the above two checks, then the score of your solution will be determined based on the speed of your code. The faster your solution is, the smaller score you get.
If you have any concerns or suggestions on this problem, please feel free to leave me a comment. Thanks.
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.
Return the largest number that is adjacent to a zero
3965 Solvers
144 Solvers
281 Solvers
Make a run-length companion vector
472 Solvers
53 Solvers
Solution 781401
Well done!