HW4 Q4
main thread
HW4 Q4
Forum
» Discussions. / Q&A, Spring 2014
» HW4 Q4
Hi,
Are there any possible inputs with a known answer that I can use, to check if my output is correct?
the only inputs that I know the answer for sure, are the basic ones (no point checking them).
thanks.
Any full board is an input for which there is a winning strategy (and therefore win() should return True).
There are also a few known simple cases for which there is no winning strategy (and therefore win() should return False) that you can use for testing.
One of them is any 2-by-m board whose single top-right corner has been munched:
win(2,m,[2]*(m-1)+[1])
Another is any n-by-n board in which only the margins are left:
win(n,n,[n]+[1]*(n-1))
I used most of these examples as base cases, thanks.
Also,
1. I didn't use m and n at all- means my code will work the same no matter what m and n are, as long as hlst is a valid input.
Is that ok?
2. Max n to check in a reasonable time, using win_memo - am I to run it once - from scratch? Because i can get further by stacking dictionary values with step-runs
I also have a question, regarding Paralaya's second question:
There are 2 ways I can think of to define the dictionary: Either globally, which means it will accumulate data between shell restarts, or locally and pass it along using envelope function- meaning data will only be kept for each call from the main environment.
My question is- are both way legit in terms of the assignment?
The are multiple ways of handling the dictionary indeed, and in class+tirgul we have seen only one of them.
Anything that works and uses memoization is fine.
The question does not require that you accumulate solutions over runs.
1. Of course. win()'s output indeed does not depend on the original board size, only on the current board configuration.
2. Measure from scratch. The idea here is not to produce the fastest possible solution, but to get a feeling for the improvement we can obtain by introducing memoization.
Hi Yael!
I couldn't get an answer to Palarya's first question about the usage of n and m.
I also did't use them at all in my code, is it ok?
Yep, definitely.
Note that m is also given to you implicitly (as the length of hlst), and I assume that your code does use it somehow.
Hi,
how can i restart the dictionary? when i try doing it threw an outer function the inner reqursive function doesnt recognize the dictionary.
tnx
eilon
Where is the dictionary declared ?
If it is declared outside of the recursive function (as in the examples we saw in class+tirgul),
you can either restart the interpreter with F5,
or reset the dictionary, e.g. as follows:
d.clear()
(this would remove all entries from a dictionary named "d").
היי, כמה שאלות קצרות:
1. הלוח ההתחלתי לא חייב להיות מלבני, נכון?
2. בהוראות כתוב: עבור לוח במצב ההתחלתי, הפונקציה תחזיר True (כי הוכחנו שלשחקן הפותח קיימת אסטרטגית ניצחון בראשית המשחק).
האם הכוונה היא רק לקונפיגורציה ההתחלתית, או שזה נכון עבור כל קונפיגורציה מלבנית באמצע המשחק?
3. בעצם כדי לגלות האם קונפיגורציה היא מנצחת, צריך לראות האם השחקן שהתחיל יכול להגיע ממנה ללוח שיש בו קובייה אחת בלבד? אני לא כל כך מבינה איך לעבוד עם זה. אשמח להבהרה
תודה,
נגה
1. נכון
2. אם התחלנו מ-[3,3,3,3] ואחרי כמה צעדים אנחנו ב- [3,3,0,0] זהו גם כן מצב התחלתי (של לוח קטן יותר) ולכן עבור כל לוח מלבני התשובה היא טרו
3. השחקן שמגיע ללוח עם קוביה אחת, מפסיד..
בגלל שקיום אסטרטגיית ניצחון (בלוח התחלתי לא מלבני/מלא) תלויה בכל פעם בצעד של היריב,
לדעתי יש צורך לבדוק את המהלך של היריב רקורסיבית:
"יש לי אסטרטגיית ניצחון אם בצעד הזה, ליריב אין אסטרטגיית ניצחון.. וכו' וכו"
עד שנגיע למקרה בסיס, כמו קוביה אחרונה
1. The original chocolate table is rectangular, and therefore a board in
מצב התחלתי
must be rectangular: In this state none of the chocolate squares have been munched yet.
2. The proof that you saw in class applies to any rectangular table, not just to a board in
מצב התחלתי
and therefore win() should return True on a rectangular board at any point during the game.
It's an important point; make sure you understand that.
3. A configuration is winning if (and only if) the player whose turn it is to play can perform a legal move that would result in a new configuration from which it is impossible to win.
Think about it, and once you are convinced try translating this to a recursive formulation.
האם ניתן לצאת מנקודת הנחה שרוחב ואורך המלבן גדולים מ1?
Technically, [3,3,2] and [3,3,2,0,0] (for example) are the same configurations. Should we treat them like the same configuration (dictionary-wise) , or is it OK if I have a separate key for each one of them?
1. The two configurations you mentioned are not equivalent. One is a legal configuration for a board with m=3, and the other is legal for a board with m=5.
2. The purpose of using a dictionary is to avoid solving the same problem multiple times. If your dictionary contains multiple key representations of the same problem, you are re-solving this problem. This is inefficient and should be avoided.
so although they are not equivalent, they represent the same problem and therefore should be represented by the same key in the dictionary?
Thanks.
It's up to the implementation.
The bottom line is that the grader will call win() with a certain board configuration, and while win() performs the computation, it must not solve the same problem twice. If your implementation modifies the values of m,n which are propagated to the recursive calls, you may find yourself solving two equivalent representations of the same problem; this should be avoided.
Perhaps this will help: Note that if the grader calls your function first on a full board of size 3-by-3, and then again on a full board of size 4-by-4, we do not except you to reuse information from the first call in the second. Just make sure not to repeat computations within the same recursive tree.
Is it right to understand that if it is my turn and the board is "full " for example [4,4,4] for m=3 n=4 so i win in this case and i may return true ?
A configuration representing a "full rectangular board" (with n+m>2) is indeed a winning configuration, as was proved in class. However, your code should not rely on this (we may take points off if it does). Instead, we recommend that you employ this fact as a sanity check for the code you write
Ok thanks and another question is ,
when in 4.b you ask me to find the biggest n that win_memo(n, n+3, [n]*(n+2)+[n-1]) will return an answer in time <= minute , Do i need to reset the dictionary after every run ?
in A it is hard to my function calculate for n>3 but my friends have better one……
is it a problem?
You mean within 1 minute you can only work on a 2-by-5 board?
It sounds to me that your code is quite inefficient, so you may want to improve it.
היי,
אני חושב על השאלה הזאת כבר למעלה מכמה ימים ואין לי כיוון בכלל.
אפשר אולי הכוונה יותר ממוקדת? במה כדאי להתמקד? והאם קיימת דרך יעילה שאינה סיבוכיות של אן ברביעית בכדי ליצור את כל קונפיגורציות המשחק שנוצרות אחרי מהלך של שחקן אחד?
תודה רבה מראש
Slides 34-35 in lecture 14 give a very thick hint to the recursive formula (i.e., how the problem can be solved given solutions to smaller similar problems). Note that they have been fixed and re-uploaded.
Mainly focus on understanding this definition: A configuration is winning if (and only if) the player whose turn it is to play can perform a legal move that would result in a new configuration from which it is impossible to win.
Having said all that, it actually sounds like you have a good direction. Testing all possible continuations indeed cannot be avoided in some cases. You do not need to generate the representations of them all in advance though, and even if you do, the complexity is not n**4.
I looked in slides 34-35 in lecture 14, and I understood that: A given configuration is winning if it has *some* legal
losing continuation.
Therefore, win(n,n,[n]+[1]*(n-1)) should be a winning continuation, doesn't it?
I mean, for n=3 hlst is [3, 1, 1] and it is possible to win (if player 2 is not so smart).
Yael said that win() should return False for this continuation, so what does it mean *some* legal
losing continuation if in this case it doesn't count?
thanks :)
For the configuration you described (as for all other 2-by-m boards with the top right square munched), all legal continuations are winning. Therefore, it is a losing configuration.
"Some" means that for a given configuration, having even only a single legal losing continuation means the given configuration is winning.
Hope this helps…
But not all legal continuations are winning…
I can describe some moves so there will be a loosing continuation. and the configuration I described is not 2-by-m boards with the top right square munched, it is n-by-n board in which only the margins are left.
for example:
Player 1 got the beginning configuration: [3,1,1]
After his move, player 2 got the configuration: [3,1,0]
After his move, player 1 got the configuration: [3,0,0]
After his move, player 2 got the configuration: [1,0,0] and player 2 is loosing
Player 1 is winning and player 2 is loosing - meaning it is a winning configuration, isn't it?
/forum/t-841665/hw4-q4#post-