☰
Home
Acht Koninginnen ★★★ Negentien Nummers Net ★★★ Ladder Laantje ★★★Kat & Muis ★★★★  [Nieuw!]Auto's Parkeren ★★★★★
Lijst van Alle PuzzelsOver deze SiteStuur een E-mailPrivacybeleid

Antwoord op: Kat & Muis

Wit kan altijd winnen als het een goede strategie hanteert (wat niet het geval was bij het spel dat je zojuist bij de puzzel hebt gespeeld). Je kunt dit zelf ervaren door hier het spel tegen de computer te spelen (klik op het veld waar je met het zwarte speelstuk naartoe wilt gaan).

Helaas, je browser ondersteunt geen HTML5.

Hieronder volgt een toelichting. Er zijn drie mogelijke uitkomsten:

  1. Ja, het spel is berekenbaar en wit kan altijd winnen.
  2. Ja, het spel is berekenbaar en zwart kan altijd winnen.
  3. Nee, het spel is niet berekenbaar.

We definiëren eerst Wwit(spelsituatie) en Wzwart(spelsituatie), die aangeven of een speler gewonnen heeft in een bepaalde spelsituatie:

We definiëren verder Cwit(speler aan zet, spelsituatie) en Czwart(speler aan zet, spelsituatie).

Cwit(speler aan zet, spelsituatie) geeft aan of wit altijd kan winnen in een spelsituatie waarin een bepaalde speler aan zet is:

Czwart(speler aan zet, spelsituatie) geeft aan of zwart altijd kan winnen in een spelsituatie waarin een bepaalde speler aan zet is:

Nu geldt:

Met vijf speelstukken en 32 velden zijn er maximaal 32 × 31 × 30 × 29 × 28 = 24.165.120 mogelijke spelsituaties. Een computerprogramma kan alle mogelijke spelverlopen dus in korte tijd doorrekenen en voor elke spelsituatie Cwit(speler aan zet, spelsituatie) en Czwart(speler aan zet, spelsituatie) bepalen. Met behulp van een dergelijk programma kan worden vastgesteld dat Cwit(zwart, beginsituatie) geldt, en dat dus wit altijd kan winnen. Hieronder staat een voorbeeld van een Python-programma dat hiervoor gebruikt kan worden.

Het is zelfs mogelijk om te berekenen hoe lang zwart het kan uithouden: als wit slim speelt, is het spel na maximaal 44 zetten voobij. 

# BSD 3-Clause License
#
# Copyright 2025 RJE-Productions and E.R. van Veldhoven
#
# Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
# following conditions are met:
#
# 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
#    disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
#    following disclaimer in the documentation and/or other materials provided with the distribution.
#
# 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
#    products derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
# INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
# USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

from enum import Enum

# We define a board of 10 by 10 fields as shown in the figure below. This board consists of an actual 8 by 8
# chessboard, surrounded by an outer ring of 'invalid' fields. The black fields of the chessboard are not used.
# In the figure, both the 'invalid' and the 'unused' fields have their numbers surrounded by brackets.
#
#   +----+----+----+----+----+----+----+----+----+----+
#   | (0)| (1)| (2)| (3)| (4)| (5)| (6)| (7)| (8)| (9)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(10)| 11 |(12)| 13 |(14)| 15 |(16)| 17 |(18)|(19)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(20)|(21)| 22 |(23)| 24 |(25)| 26 |(27)| 28 |(29)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(30)| 31 |(32)| 33 |(34)| 35 |(36)| 37 |(38)|(39)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(40)|(41)| 42 |(43)| 44 |(45)| 46 |(47)| 48 |(49)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(50)| 51 |(52)| 53 |(54)| 55 |(56)| 57 |(58)|(59)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(60)|(61)| 62 |(63)| 64 |(65)| 66 |(67)| 68 |(69)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(70)| 71 |(72)| 73 |(74)| 75 |(76)| 77 |(78)|(79)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(80)|(81)| 82 |(83)| 84 |(85)| 86 |(87)| 88 |(89)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(90)|(91)|(92)|(93)|(94)|(95)|(96)|(97)|(98)|(99)|
#   +----+----+----+----+----+----+----+----+----+----+
#
# The figure below only shows the numbers of the 32 used fields:
#
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 11 |    | 13 |    | 15 |    | 17 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 22 |    | 24 |    | 26 |    | 28 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 31 |    | 33 |    | 35 |    | 37 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 42 |    | 44 |    | 46 |    | 48 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 51 |    | 53 |    | 55 |    | 57 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 62 |    | 64 |    | 66 |    | 68 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 71 |    | 73 |    | 75 |    | 77 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 82 |    | 84 |    | 86 |    | 88 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#
# White starts on the fields 11, 13, 15, and 17. We store the positions of the white pieces in the 'whitePositions'
# array. Black starts on field 84, and we store its position in the 'blackPosition' variable.
#
# White can make the following two moves:
# 1. one field diagonally down to the left: this corresponds to an increase of the field number by 9.
# 2. one field diagonally down to the right: this corresponds to an increase of the field number by 11.
#
# Black can make the following four moves:
# 1. one field diagonally down to the left: this corresponds to an increase of the field number by 9.
# 2. one field diagonally down to the right: this corresponds to an increase of the field number by 11.
# 3. one field diagonally up to the left: this corresponds to a decrease of the field number by 11.
# 4. one field diagonally up to the right: this corresponds to a decrease of the field number by 9.
#
# A move is only valid if there is not already a piece on the destination field and the destination field is not on
# the outer ring. A field lies on the outer ring if any of the following conditions hold:
# - the field number is less than 10;
# - the field number is at least 90;
# - the field number modulo 10 equals 0;
# - the field number modulo 10 equals 9.
#
# We store the result for each game situation in the variable "outcomes". This variable contains the outcome for
# each combination (player to move, position of black, positions of white pieces 1 to 4). We map the 32 possible
# field numbers to the range [0..31] as follows:
#
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |  0 |    |  1 |    |  2 |    |  3 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |  4 |    |  5 |    |  6 |    |  7 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |  8 |    |  9 |    | 10 |    | 11 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 12 |    | 13 |    | 14 |    | 15 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 16 |    | 17 |    | 18 |    | 19 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 20 |    | 21 |    | 22 |    | 23 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 24 |    | 25 |    | 26 |    | 27 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 28 |    | 29 |    | 30 |    | 31 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+


NR_OF_POSITIONS = 32  # There are 32 fields on which the pieces can be positioned.
POSSIBLE_MOVES = [9, 11, -11, -9]

# Define a mapping of the 32 usable field numbers in the range [0..99] to the range [0..31].
MAPPING = [
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, -1, 2, -1,
    3, -1, -1, -1, -1, 4, -1, 5, -1, 6, -1, 7, -1, -1, 8, -1, 9, -1,
    10, -1, 11, -1, -1, -1, -1, 12, -1, 13, -1, 14, -1, 15, -1, -1,
    16, -1, 17, -1, 18, -1, 19, -1, -1, -1, -1, 20, -1, 21, -1, 22, -1,
    23, -1, -1, 24, -1, 25, -1, 26, -1, 27, -1, -1, -1, -1, 28, -1,
    29, -1, 30, -1, 31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
]


class Player(Enum):
    BLACK = 0
    WHITE = 1


class Outcome(Enum):
    NOT_CALCULATED = 0
    BLACK_CAN_ALWAYS_WIN = 1
    WHITE_CAN_ALWAYS_WIN = 2
    BEING_CALCULATED = 3


class CatAndMouseGame:
    def __init__(self):
        # 'outcomes' corresponds to C_white(player whose move it is, game situation)
        # and C_black(player whose move it is, game situation) in the puzzle explanation.
        self.outcomes = [[[[[[Outcome.NOT_CALCULATED for _ in range(NR_OF_POSITIONS)]
                            for _ in range(NR_OF_POSITIONS)]
                            for _ in range(NR_OF_POSITIONS)]
                           for _ in range(NR_OF_POSITIONS)]
                          for _ in range(NR_OF_POSITIONS)]
                         for _ in range(2)]

        self.black_position = 0  # Initialize with a default value
        self.white_positions = [0] * 4
        self.total = 0
        self.initialize_piece_positions()

    def initialize_piece_positions(self):
        self.black_position = 84
        self.white_positions = [11, 13, 15, 17]

    def show_progress(self):
        self.total += 1
        if self.total % 10000 == 0:
            print(self.total, end='\r')

    def is_usable_field(self, field_number):
        if field_number < 10 or field_number >= 90 or field_number % 10 == 0 or field_number % 10 == 9:
            # The field is on the outer ring
            return False
        else:
            # Check if in this row the usable fields have odd numbers (this holds for rows 2, 4, 6, and 8)
            odd_row = (field_number // 10) % 2 == 1
            return (odd_row and field_number % 2 == 1) or (not odd_row and field_number % 2 == 0)

    def is_move_allowed(self, piece_position: int, move: int) -> bool:
        new_piece_position = piece_position + move

        if not self.is_usable_field(new_piece_position):
            # A move outside the chessboard is not allowed
            return False

        if new_piece_position == self.black_position:
            # Black is on the new field, therefore the move is not allowed
            return False

        for white in range(4):
            if new_piece_position == self.white_positions[white]:
                # A white piece is on the new field, therefore the move is not allowed
                return False

        return True

    def black_has_won(self) -> bool:
        return self.black_position in [11, 13, 15, 17]

    def white_has_won(self) -> bool:
        # White wins if it blocks black in such a way that black cannot make any move anymore
        return not (self.is_move_allowed(self.black_position, POSSIBLE_MOVES[0]) or
                    self.is_move_allowed(self.black_position, POSSIBLE_MOVES[1]) or
                    self.is_move_allowed(self.black_position, POSSIBLE_MOVES[2]) or
                    self.is_move_allowed(self.black_position, POSSIBLE_MOVES[3]))

    def white_can_make_a_move(self) -> bool:
        return (self.is_move_allowed(self.white_positions[0], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[0], POSSIBLE_MOVES[1]) or
                self.is_move_allowed(self.white_positions[1], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[1], POSSIBLE_MOVES[1]) or
                self.is_move_allowed(self.white_positions[2], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[2], POSSIBLE_MOVES[1]) or
                self.is_move_allowed(self.white_positions[3], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[3], POSSIBLE_MOVES[1]))

    def get_outcome(self, player: Player, black_position: int, white_positions: list) -> Outcome:
        # Because the white pieces are interchangeable, we can sort their positions for more efficient calculation
        sorted_white_positions = sorted(white_positions)
        return self.outcomes[player.value][
            MAPPING[black_position]][
            MAPPING[sorted_white_positions[0]]][
            MAPPING[sorted_white_positions[1]]][
            MAPPING[sorted_white_positions[2]]][
            MAPPING[sorted_white_positions[3]]]

    def set_outcome(self, player: Player, black_position: int, white_positions: list, outcome: Outcome):
        # Because the white pieces are interchangeable, we can sort their positions for more efficient calculation
        sorted_white_positions = sorted(white_positions)
        self.outcomes[player.value][
            MAPPING[black_position]][
            MAPPING[sorted_white_positions[0]]][
            MAPPING[sorted_white_positions[1]]][
            MAPPING[sorted_white_positions[2]]][
            MAPPING[sorted_white_positions[3]]] = outcome

    def white_move(self):
        self.show_progress()
        white_can_win = False
        black_can_win = False

        if self.white_can_make_a_move():
            for piece in range(4):
                for move in range(2):
                    if self.is_move_allowed(self.white_positions[piece], POSSIBLE_MOVES[move]):
                        # Perform the white move
                        tmp_position = self.white_positions[piece]
                        self.white_positions[piece] += POSSIBLE_MOVES[move]

                        # Now black is to move
                        outcome = self.get_outcome(
                            Player.BLACK, self.black_position, self.white_positions)

                        if outcome == Outcome.NOT_CALCULATED:
                            # This game situation has not been calculated yet
                            if self.white_has_won():
                                self.set_outcome(Player.BLACK, self.black_position,
                                                 self.white_positions, Outcome.WHITE_CAN_ALWAYS_WIN)
                            else:
                                self.black_move()

                            outcome = self.get_outcome(
                                Player.BLACK, self.black_position, self.white_positions)

                        if outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
                            white_can_win = True
                        elif outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
                            black_can_win = True

                        # Restore the game situation
                        self.white_positions[piece] = tmp_position
        else:
            # If white cannot move, it must skip a turn
            # Now black is to move
            outcome = self.get_outcome(
                Player.BLACK, self.black_position, self.white_positions)

            if outcome == Outcome.NOT_CALCULATED:
                # Prevent endless loops
                self.set_outcome(Player.BLACK, self.black_position,
                                 self.white_positions, Outcome.BEING_CALCULATED)
                self.black_move()
                outcome = self.get_outcome(
                    Player.BLACK, self.black_position, self.white_positions)

            if outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
                white_can_win = True
            elif outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
                black_can_win = True

        if white_can_win:
            self.set_outcome(Player.WHITE, self.black_position, self.white_positions,
                             Outcome.WHITE_CAN_ALWAYS_WIN)
        elif black_can_win:
            self.set_outcome(Player.WHITE, self.black_position, self.white_positions,
                             Outcome.BLACK_CAN_ALWAYS_WIN)

    def black_move(self):
        self.show_progress()
        black_can_win = False
        white_can_win = False

        for move in range(4):
            if self.is_move_allowed(self.black_position, POSSIBLE_MOVES[move]):
                # Perform the black move
                tmp_position = self.black_position
                self.black_position += POSSIBLE_MOVES[move]

                # Now white is to move
                outcome = self.get_outcome(
                    Player.WHITE, self.black_position, self.white_positions)

                if outcome == Outcome.NOT_CALCULATED:
                    # This game situation has not been calculated yet
                    if self.black_has_won():
                        self.set_outcome(Player.WHITE, self.black_position,
                                         self.white_positions, Outcome.BLACK_CAN_ALWAYS_WIN)
                    else:
                        self.white_move()

                    outcome = self.get_outcome(
                        Player.WHITE, self.black_position, self.white_positions)

                if outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
                    black_can_win = True
                elif outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
                    white_can_win = True

                # Restore the game situation
                self.black_position = tmp_position

        if black_can_win:
            self.set_outcome(Player.BLACK, self.black_position, self.white_positions,
                             Outcome.BLACK_CAN_ALWAYS_WIN)
        elif white_can_win:
            self.set_outcome(Player.BLACK, self.black_position, self.white_positions,
                             Outcome.WHITE_CAN_ALWAYS_WIN)


print("Creating game object...")
game = CatAndMouseGame()

print("Running game...")
game.black_move()

print(game.total)
game.initialize_piece_positions()
print(game.get_outcome(Player.BLACK, game.black_position, game.white_positions).name)

Terug naar de puzzel
×
OK