Page 1 of 1

10838 - The Pawn Chess

Posted: Mon Mar 21, 2005 5:25 pm
by Dreamer#1
Are there any special cases in this problem? I can't find any! a plain solution should have taken care of everything but unfortunately I'm getting WA. :(

Can someone please verify the following cases:

Code: Select all


Input:

8

....
..p.
pp..
P.P.

p.pp
....
P...
P...

.pp.
....
....
.P..

.pp.
...p
..P.
...P

..p.
.pPp
....
...P


pppp
....
....
PPPP

..p.
....
...P
P...

....
....
.p..
P...


Output:

black (4)
black (4)
black (2)
black (4)
black (2)
white (11)
white (3)
white (1)


If the above are ok then can someone please give cases that might be more tricky.

Thanks in advance.

Posted: Mon Mar 21, 2005 6:15 pm
by stubbscroll
Your output is correct. I don't think there are any special cases, the only potential special case I could think of is not legal (black already won, "black (0)"). If you didn't hardcode your program to 4 pawns or less, you might want to try this (also illegal input):

Code: Select all

1

pppp
pppp
PPPP
PPPP
Output: white (15)

Posted: Mon Mar 21, 2005 7:36 pm
by SilentStrike
I had a bug because I was trying to encode the states into a 32 bit integer, and there was some problems in storing the pawn in the bottom right (most signficant two bits in my integer). If you are encoding into an int, try using 64 bits for safety.

Posted: Mon Mar 21, 2005 8:19 pm
by Dreamer#1
Thanks... Got AC. :D
But I need to stop listening to music while coding. :oops:

10838 - The Pawn Chess

Posted: Tue Mar 22, 2005 9:02 pm
by jagadish
Can someone tell me how to optimize this program genuinely ? i used some cached values to pass the test data(1.84 sec )..a few of them have got less than 0.01s :-?

Posted: Thu Mar 24, 2005 7:05 pm
by SilentStrike
Was it a 32 bit overflow problem?

Posted: Sun Apr 17, 2005 6:11 pm
by Niaz
I can't understand the overflow problem.
And can u plz tell me, is there any special method to solve this problem or just simply Adhok solution can do ?

Posted: Mon Apr 18, 2005 12:21 am
by SilentStrike
I wrote up my solution to the Pawn Chess problem on Algorithmist.

The 32 bit overflow problem is basically that you might overflow an int when doing bit arithmetic to pack a state into a 32 bit int.

Posted: Wed Nov 09, 2005 5:06 pm
by Christian Schuster
I tried to solve this problem by using a minimax search. Each game state is assigned a value recursively:

Code: Select all

 0 <= N <= 19: BLACK wins after N moves
20 <= N <= 39: WHITE wins after (39-N) moves
Winning states get a 0 or 39, depending on the winner. For any other game state, BLACK uses the child state with the lowest score, while WHITE uses the highest.

This seems quite correct to me, and returns the correct output for any input in this thread. However, the judge disagrees (WA).

What's wrong? The "Algorithmist" solution seem quite similar, apart from using another encoding for the winner/moves value.

Posted: Wed Nov 09, 2005 6:43 pm
by Cho
Here are some random input: 10838.zip
Please ignore those cases with "black (0)" as output, judge's input should not contain such cases.

Posted: Thu Nov 10, 2005 3:27 pm
by Christian Schuster
Thank you. I had alpha-beta pruning enabled in my code, but this does not work if values are changed when passing them up the game tree. Something like this is necessary for the "fast victory/slow defeat" strategy to work.

Finally, I got AC in 2.38s using "normal" minimax.

Posted: Fri Nov 11, 2005 1:33 am
by Krzysztof Duleba
Actually, my number-one code (completely unoptimized, it could run at least two times faster) is using alpha-beta.