Kings on a Chessboard

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Kings on a Chessboard

Postby emlightened » Sat Sep 26, 2015 10:21 pm UTC

Suppose there are two kings (W and B) on opposite corners of a chessboard:

Code: Select all

W░▓░▓░▓░
░▓░▓░▓░▓
▓░▓░▓░▓░
░▓░▓░▓░▓
▓░▓░▓░▓░
░▓░▓░▓░▓
▓░▓░▓░▓░
░▓░▓░▓░Y


White goes first. The kings may only move to adjacent and diagonally adjacent squares. Once a king moves onto a square, neither player can move onto that square again. The first player that has no moves available loses.

Kings are not allowed to move into check.

Assuming optimum play, which player wins?

Edit: Added that kings are not allowed to move into check, and relabelled X and Y to White and Black, to make things clearer.
Last edited by emlightened on Sun Sep 27, 2015 5:34 pm UTC, edited 1 time in total.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Kings on a Chessboard

Postby jestingrabbit » Sun Sep 27, 2015 1:48 am UTC

This actually looks like a new puzzle to me. And, if I've got the answer right, its quite neat.

Spoiler:
Y mirrors X ie X's moves can be written as compass moves (N, NE, E, SE, S, SW, W, NW), and Y translates those moves into (S, SW, W, NW, N, NE, E, SE), so the board always has 180 degree symmetry, and so whenever X can move, Y can move.

Relates back to an old favourite. http://www.forums.xkcd.com/viewtopic.php?f=3&t=155


redundant with the check rule.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Kings on a Chessboard

Postby Gwydion » Sun Sep 27, 2015 3:14 pm UTC

I agree with Jestingrabbit, but only if the kings only care about the spaces they're on. If we add the rules of chess, meaning kings can't move into check, that solution could fail- as soon as white moves into rows 4-5 in columns D-E, black can't legally follow but might have other asymmetric moves. I still think white can force a win but can't prove it yet...

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: Kings on a Chessboard

Postby emlightened » Sun Sep 27, 2015 5:32 pm UTC

Sorry, I did mean to add that the kings can't move into check. Editing now.

Not exactly sure how to approach this. Do you want to try to stay one away from the edge of the board, to stop the opponent from going that way, whilst still being able to go down it yourself?

"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."

User avatar
measure
Posts: 129
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Kings on a Chessboard

Postby measure » Tue Sep 29, 2015 10:56 pm UTC

This seems remarkably similar to Tron, except with alternating discrete movement.

Yrgos
Posts: 6
Joined: Fri Nov 06, 2015 10:33 pm UTC

Re: Kings on a Chessboard

Postby Yrgos » Fri Nov 06, 2015 11:05 pm UTC

Is an exhaustive search of the game tree possible? Max number of moves is 62 and the will only be a few times where you have 7 spaces to go to, most times quite a few less.

Perhaps an intelligent exhaustive search where you start with landgrabbing and play "intelligently"

taemyr
Posts: 111
Joined: Fri Jan 26, 2007 12:14 pm UTC

Re: Kings on a Chessboard

Postby taemyr » Thu Nov 12, 2015 9:15 am UTC

Yrgos wrote:Is an exhaustive search of the game tree possible? Max number of moves is 62 and the will only be a few times where you have 7 spaces to go to, most times quite a few less.

Perhaps an intelligent exhaustive search where you start with landgrabbing and play "intelligently"


Exhaustive search is not feasible.

7^62=2.48*10^52

However as you not there will be a lot of cases where one have less than 7 moves available. This helps, but not enough. If we assume a geometric mean of 4 for the number of available moves we get 4^62=2.13*10^37 different game lines.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 10 guests