10838 - The Pawn Chess

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

10838 - The Pawn Chess

Post by Dreamer#1 » Mon Mar 21, 2005 5:25 pm

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.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Mon Mar 21, 2005 6:15 pm

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)

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

Post by SilentStrike » Mon Mar 21, 2005 7:36 pm

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.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Mon Mar 21, 2005 8:19 pm

Thanks... Got AC. :D
But I need to stop listening to music while coding. :oops:

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

10838 - The Pawn Chess

Post by jagadish » Tue Mar 22, 2005 9:02 pm

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 :-?
if u can think of it .. u can do it in software.

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

Post by SilentStrike » Thu Mar 24, 2005 7:05 pm

Was it a 32 bit overflow problem?

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Sun Apr 17, 2005 6:11 pm

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 ?
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

Post by SilentStrike » Mon Apr 18, 2005 12:21 am

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.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Wed Nov 09, 2005 5:06 pm

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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Nov 09, 2005 6:43 pm

Here are some random input: 10838.zip
Please ignore those cases with "black (0)" as output, judge's input should not contain such cases.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Thu Nov 10, 2005 3:27 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Nov 11, 2005 1:33 am

Actually, my number-one code (completely unoptimized, it could run at least two times faster) is using alpha-beta.

Post Reply

Return to “Volume 108 (10800-10899)”