作者pttworld (批踢踢世界)
看板Prob_Solve
标题Re: [问题] leetcode 464 can i win
时间Sat May 20 06:39:06 2017
1. 玩家1和玩家2交替选择数字。
第一次到第三次选择会是玩家1，玩家2，玩家1。
对於第三次选择的时候，
第一次选1，第二次选2和第一次选2，第二次选1，实际上是没有差别的。
使用map纪录1和2被选的样态，相同样态直接取结果对递回截枝。
2. 最佳化的判断，在所有可能有一成立即成立，直接函数返回加速。
AC, 1s
https://github.com/jamalch-tw/oj/blob/master/LeetCode/464.cpp
※ 引述《powertodream (The Beginning)》之铭言：
: https://leetcode.com/problems/can-i-win/#/description
: 是两个人互相取数字, 当第一个人取的数字超过目标, 就return true
: 原本的想法是, player 1 挑全部没选过的number, 然後 呼叫secondPlayerWin的
: function
: 去判断是不是有存在secondPlayer win的, 只要有存在A 选的这个number就是不行的
: 不过写不太好的吃了个wrong answer,
: 偷看看讨论串解答
: 看了很多的作法, 都是做类似
: !helper(desiredTotal - i)
: 的递回,
: 想半天仍然不太懂... 有版友有兴趣一起研究研究吗?
: 这个是原作者的解释, 但是我仍然不懂他的意思, 为什麽code要写成那样
: **
: The strategy is we try to simulate every possible state. E.g. we let this
: player choose any unchosen number at next step and see whether this leads to
: a win. If it does, then this player can guarantee a win by choosing this
: number. If we find that whatever number s/he chooses, s/he won't win the
: game, then we know that s/he is guarantee to lose given such a state.
: // try every unchosen number as next step
: for(int i=1; i<used.length; i++){
: if(!used[i]){
: used[i] = true;
: // check whether this lead to a win, which means
: helper(desiredTotal-i) must return false (the other player lose)
: if(!helper(desiredTotal-i)){
: map.put(key, true);
: used[i] = false;
: return true;
: }
: used[i] = false;
: }
: }
: map.put(key, false);
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.43.36.13
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1495233549.A.DC9.html
1F：推 powertodream: 我这边卡住的点是 b如果没选到最佳的 可能a就赢了 05/21 02:51
2F：→ powertodream: 所以感觉不能穷举全部选择 不知道该如何处理? 05/21 02:51
3F：推 powertodream: 看你的做法是全部考虑？ 所以是我哪边想错了吗？ 05/21 02:54
题目规定双方皆为最佳玩法，思路必须相对：
如果a找到最佳，b就输了；如果b找到最佳，a就输了。
有找到就返回是考虑全部的提速。
※ 编辑: pttworld (115.43.36.13), 05/21/2017 16:38:42
4F：推 powertodream: 好像有点懂了 我在想一下XD 05/21 19:24
5F：→ powertodream: 不过你的做法跟我看不懂那个应该是等价的 05/21 19:24
6F：→ powertodream: 只是他合成同一个, 比较难懂, 你的分开player处理 05/21 19:24
7F：→ powertodream: 比较容易看懂 XD 05/21 19:25
9F：→ FRAXIS: 使用 map 的技术叫做 transposition table 05/21 21:46
11F：推 powertodream: 也太复杂, 一堆词都没听过...谢谢各位 我研究研究 05/21 22:47
12F：推 LPH66: negamax 的原理其实就只是 min(a,b) = -max(-a,-b) 05/22 01:30
13F：→ LPH66: 所以 min 层的动作可以跟 max 层动作相同但取负号 05/22 01:30
14F：→ LPH66: 其实这以 min 层玩家的视点来看也是很合理的 05/22 01:30
15F：→ LPH66: 对对手极好的结果对自己就是极糟 05/22 01:31
16F：→ LPH66: 於是就能把「最小化对手得分」转化成「最大化"自己"得分」 05/22 01:32
17F：→ LPH66: 以最大化自己得分这个观点来说两个玩家的动作其实是一样的 05/22 01:33
18F：→ LPH66: 把以上这一些总结起来就是 negamax 演算法了 05/22 01:33
19F：推 cutekid: 推 L 大，「零和游戏」利用取负号(取代min、max层的判断) 05/22 16:27