1

This is a game for 2 people to remove numbers from a list. A player will lose if the player picks up the last number. Given the 2 rules of removing numbers in a list,

  1. Prolog search for possible combination for subtracting 2 elements from a list
  2. Prolog possible removal of elements in a list

There is a question,

write a predicate win(S), that succeed if S is a winning position for the player whose turn it is to play and fails otherwise. Besides giving the correct answers, your code for this should avoid evaluating the same position more than once. For example, there are only 960 positions that can be reached from [30,30], but many billions of games that could be played starting from there...

I am really confused how can [30,30] reach 960 positions. According to the 2 rules, if I subtract N from one element only, I can only reach 60 states.

Y = [29, 30]  or  Y = [30, 29]
Y = [28, 30]  or  Y = [30, 28]
Y = [27, 30]  or  ...
...
Y = [1, 30]
Y = [30]

Or If I subtract N from 2 elements, I can only reach 30 states..

Y = [29, 29]
Y = [28, 28]
...
Y = [1, 1]
Y = []

I am really confused how 960 position can be reached. Yet, win(S), will evaluate whether the S is a winning position... Does it mean that current S can directly leads to [1] by just one move? or the current S can lead to [1] by multiple moves?

Community
  • 1
  • 1
user3390652
  • 132
  • 1
  • 13
  • You've miscounted the number of possible states in your first example. Your "or" is deceiving you thinking that each row is just two states, but each "or" branches into it's own list of new alternatives. Think of it as a 2 digit number in base 31 (the "digits" are 0 to 30). So you'd have 31*31 combinations or 2-digit numbers, minus the 0 case, which is 960. – lurker Nov 15 '15 at 20:11
  • @lurker I see. So it is saying all possible states until it can reach [1]. I hope I am getting it correctly. But what do you think winning position mean here? – user3390652 Nov 15 '15 at 23:23
  • I'm not sure what the game rules are. You gave a couple of links, but those are to two other questions about reducing elements in list but don't say anything about game rules. How are the rules stated? – lurker Nov 15 '15 at 23:28
  • @lurker Actually, it describes the elements as heaps. And there are N stones in each heaps.[10,9,8], so, heap1 = 10 stones, heap2 = 9 stones, so on. According to my links, I have 2 ways to remove these stones. The first one is removing N stones from any single heap, the second rule is removing N stones from any 2 heaps. These are essentially the same as my 2 previous questions. And 2 players are removing stones following these 2 rules in his turn. A player is lost if he picks up the last stone. – user3390652 Nov 15 '15 at 23:39
  • @lurker I was reluctant to post the exact wordings as stated on the coursework sheet as I am afraid of being plagiarism. Anyway, I think it is fine now.. as I am not copy and pasting the code answered by others here.. – user3390652 Nov 15 '15 at 23:41
  • Does the description above make sense? – user3390652 Nov 15 '15 at 23:47
  • So the player loses if they are "stuck with" the `[1]`. So the winner would need to "force" the sequence toward `[1]` for the other player's turn. – lurker Nov 15 '15 at 23:50
  • @lurker yes. This is how it works. However, I am stuck with "winning position". I do not understand whether `win(S)` means S can lead to `[1]` by making just one moves or more than one moves.. – user3390652 Nov 16 '15 at 00:02
  • For the quotation block in the question, it is the exact question as printed on the coursework sheet... – user3390652 Nov 16 '15 at 00:03
  • `S` would be a state of `[X, Y]` that would be a state you leave for the other player. That is, supposing you made some move leaving `[X,Y]` it can inevitably lead to the other player losing as long as you make all the right moves in between. – lurker Nov 16 '15 at 00:08
  • in case of leaving `[2,1]`, should `win([2,1])` return true or false? And, as S is just some possible states, how would it be possible to evaluate the same position more than once? – user3390652 Nov 16 '15 at 00:17
  • I would think `win([2,1])` is false since the other player an subtract `2` from the first element leaving you with `[1]` which would mean you lost. – lurker Nov 16 '15 at 00:29
  • @lurker I had talked with my professor yesterday, and he said that the question is actually talking about whether S is a winning state of a player. So, for example, game starting from `[3, 3]`. Player A makes a move to [2,2], and Player B lost because player B must pick up the last stone. And in this case, win([3,3]) should return true. After that , I have read a few searching algorithm, and I have decided to go with A * algorithm. I will update here after I have done that. lol – user3390652 Nov 17 '15 at 12:45
  • OK that interpretation makes sense. – lurker Nov 17 '15 at 12:49
  • The way to interpret this problem logically is: (1) you assume the starting state is your move, (2) you want to succeeds only on sequences of states such that *at least one* legal move on your part at each step and *any* legal move on the opponents part at each step leads you to `[1]` for the opponent. – lurker Nov 17 '15 at 13:22

0 Answers0