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
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

10838 - The Pawn Chess

Post 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.

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

Post 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)

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

Post 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.

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

Post by Dreamer#1 »

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 »

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 »

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 »

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 »

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.

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

Post 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.

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

Post 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.

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

Post 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.

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

Post by Krzysztof Duleba »

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)”