Problem 42674. Cody meets Xiangqi: foresee the unseen (Part 1)

Created by Peng Liu

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is the first part of the Xiangqi series. The second part in this series is:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/42685-cody-meets-xiangqi-foresee-the-unseen-part-2\"><w:r><w:t>Cody meets Xiangqi: foresee the unseen (Part 2)</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Xiangqi\"><w:r><w:t>Xiangqi</w:t></w:r></w:hyperlink><w:r><w:t>, also known as</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>Chinese Chess</w:t></w:r><w:r><w:t> (and 象棋 in Chinese characters), is one of the most popular board games in China. The modern Xiangqi board contains a middle section which divides two players' sides and is marked the \"Chu River–Han border\", in reference to the Chu–Han Contention between</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Xiang_Yu\"><w:r><w:t>Xiang Yu</w:t></w:r></w:hyperlink><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://de.wikipedia.org/wiki/Han_Gaozu\"><w:r><w:t>Liu Bang</w:t></w:r></w:hyperlink><w:r><w:t>, two prominent warlords and opponents who fought thousands of battles against each other for supremacy over China in the late Qin dynasty (206–202 BC). Those interested in the story of the Chu–Han Contention and its relation to Xiangqi are referred to</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Chu%E2%80%93Han_Contention\"><w:r><w:t>here</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Fresh to Xiangqi, Cody becomes interested in Xiangqi by raising a question:</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Who is the stronger player of Xiangqi between Xiang Yu and Liu Bang</w:t></w:r><w:r><w:t>? To answer this question, Cody designs a match for Xiang Yu and Liu Bang, in which Cody serves as the referee. The smart Cody referee also sets an intelligent rule to determine the winner:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>In a succession of Xiangqi games, once Xiang Yu wins Na games</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>consecutively</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>, whereas Liu Bang has not won Nb games</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>consecutively</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>, Cody immediately announces Xiang Yu as the winner. Contrarily, once Liu Bang defeats Xiang Yu Nb times</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>consecutively</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>, whereas Xiang Yu has not won Na times</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>consecutively</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>, Liu Bang becomes the winner.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Cody suggests that Na &gt; 1 and Nb &gt; 1, in order to enhance, to some extent, the confidence of the result of the match. Suppose in each individual game, the probability Xiang Yu would win is p, and the probability Liu Bang would win is 1 - p, which implicitly assumes that the probability of a tie is 0 (because they both refuse to draw and will fight to death). Unfortunately, this well-designed match has never taken place. Regretfully, Cody requests us --- active Cody players --- to foresee the outcome of this unseen match using Monte Carlo simulations. Our task is to write a function</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ sol = Xiangqi(p, Na, Nb)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>with input: 0 &lt;= p &lt;= 1, Na &gt; 1, Nb &gt; 1, and output: sol --- the probability that Xiang Yu wins. Your solution will be tested against its true value Q (which is computed but hided in the P-file EvaluateSolution.p) according to a hybrid absolute and relative error tolerance criterion:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ abs(sol - Q) <= max(AbsTol, RelTol*abs(sol))]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>where AbsTol and RelTol are absolute and relative error tolerances, respectively, which will be specified in the test suite. You are encouraged to optimize the performance (rather than the usual Cody size) of your code as much as possible, as the score of your solution will be measured based on the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>speed</w:t></w:r><w:r><w:t> of your code.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Have fun!</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This is the first part of the Xiangqi series. The second part in this series is: <a href = "http://www.mathworks.com/matlabcentral/cody/problems/42685-cody-meets-xiangqi-foresee-the-unseen-part-2">Cody meets Xiangqi: foresee the unseen (Part 2)</a><a href = "https://en.wikipedia.org/wiki/Xiangqi">Xiangqi</a>, also known as Chinese Chess (and 象棋 in Chinese characters), is one of the most popular board games in China. The modern Xiangqi board contains a middle section which divides two players' sides and is marked the "Chu River–Han border", in reference to the Chu–Han Contention between <a href = "https://en.wikipedia.org/wiki/Xiang_Yu">Xiang Yu</a> and <a href = "https://de.wikipedia.org/wiki/Han_Gaozu">Liu Bang</a>, two prominent warlords and opponents who fought thousands of battles against each other for supremacy over China in the late Qin dynasty (206–202 BC). Those interested in the story of the Chu–Han Contention and its relation to Xiangqi are referred to <a href = "https://en.wikipedia.org/wiki/Chu%E2%80%93Han_Contention">here</a>.Fresh to Xiangqi, Cody becomes interested in Xiangqi by raising a question: Who is the stronger player of Xiangqi between Xiang Yu and Liu Bang? To answer this question, Cody designs a match for Xiang Yu and Liu Bang, in which Cody serves as the referee. The smart Cody referee also sets an intelligent rule to determine the winner:In a succession of Xiangqi games, once Xiang Yu wins Na games consecutively, whereas Liu Bang has not won Nb games consecutively, Cody immediately announces Xiang Yu as the winner. Contrarily, once Liu Bang defeats Xiang Yu Nb times consecutively, whereas Xiang Yu has not won Na times consecutively, Liu Bang becomes the winner.Cody suggests that Na &gt; 1 and Nb &gt; 1, in order to enhance, to some extent, the confidence of the result of the match. Suppose in each individual game, the probability Xiang Yu would win is p, and the probability Liu Bang would win is 1 - p, which implicitly assumes that the probability of a tie is 0 (because they both refuse to draw and will fight to death). Unfortunately, this well-designed match has never taken place. Regretfully, Cody requests us --- active Cody players --- to foresee the outcome of this unseen match using Monte Carlo simulations. Our task is to write a function<pre> sol = Xiangqi(p, Na, Nb)</pre>with input: 0 &lt;= p &lt;= 1, Na &gt; 1, Nb &gt; 1, and output: sol --- the probability that Xiang Yu wins. Your solution will be tested against its true value Q (which is computed but hided in the P-file EvaluateSolution.p) according to a hybrid absolute and relative error tolerance criterion:<pre> abs(sol - Q) &lt;= max(AbsTol, RelTol*abs(sol))</pre>where AbsTol and RelTol are absolute and relative error tolerances, respectively, which will be specified in the test suite. You are encouraged to optimize the performance (rather than the usual Cody size) of your code as much as possible, as the score of your solution will be measured based on the speed of your code.Have fun!

Solve

Solution Stats

54 Solutions
8 Solvers

Last Solution submitted on Aug 07, 2019

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Problem Tags

Problem 42674. Cody meets Xiangqi: foresee the unseen (Part 1)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author30

Problem Tags

Problem 42674. Cody meets Xiangqi: foresee the unseen (Part 1)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author30

Problem Tags

Players