| |
| Autor |
  Bundeswettbewerb Mathematik 2015 |
|
Kollodez777
Senior 
Dabei seit: 15.07.2014
Mitteilungen: 1522
 |  Themenstart: 2015-09-24
|
Hallo,
es gab einige Schwierigkeiten in einem Thread auf der Seite ,,Uni-Protokolle.de'', weswegen einige Mitglieder sich dazu entschlossen haben auf dem Matheplaneten weiter zu schreiben und den Erfahrungsaustausch hier fortzuführen.
Viel Spaß beim Erfahrungsaustausch (ohne Schwierigkeiten :-D )
MfG
K7
|
 Profil
|
ZetaX
Senior 
Dabei seit: 24.01.2005
Mitteilungen: 2804
Wohnort: Wenzenbach
 |  Beitrag No.1, eingetragen 2015-09-25
|
Falls ihr Erfahrungen und dergleichen zum BWM sucht, so gibt es dazu mehrere Threads vergangener Jahre, zu finden hier.
|
Profil
|
Kollodez777
Senior
Dabei seit: 15.07.2014
Mitteilungen: 1522
| Beitrag No.2, vom Themenstarter, eingetragen 2015-09-25
|
Hallo ZetaX,
danke für diese Information :-)
An @maßtensor (wie er noch bei Uniprotokolle hieß):
Wow, das finde ich interessant, dass Anja für ein 9x2 Rechteck keinerlei Chance hat zu gewinnen (nach deinem Programm ;-) (bezieht sich auf die erste Aufgabe des BWM 2015 in der zweiten Runde)) :-o
Außerdem sind die Lösungen online. Die Lösung zu 1 hat ohnehin jeder so :-D
Zu 2: Den eleganten Beweis fand ich fantastisch (dass man das so kurz fassen kann :-o ).
Zu 3: Ich fand es offensichtlich, dass man die Behauptung mit der Vollständigen Induktion zeigen kann, war aber zu faul dafür, weswegen ich es mit Rekursionen gemacht habe ^^
Zu 4: Meine Meinung nach ist das einer der ,,hässlichsten'' aufgaben, die ich je gesehen habe und das sogar für Geometrie-Aufgaben :-D
Und zu Kezer: Das ist nur die vorläufige Fassung, vielleicht kommt dein geometrischer Beweis doch noch dazu :-D
Das von meiner Seite aus ^^
MfG
K7
|
Profil
|
umlaufsatz
Senior 
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.3, eingetragen 2015-09-25
|
Hallo zusammen,
ich bin maßtensor von uni-protokolle.de und heiße hier jetzt umlaufsatz, weil das Forum nur a-z, A-Z und 0-9 als Zeichen im Nutzernamen nimmt. Um Verwirrung zu vermeiden, nennt mich bitte umlaufsatz :).
Dieses Forum scheint ja ungewöhnlich reich an Funktionen zu sein :). Es sprüht geradezu an Funktionalität, so sieht es aus. Man kann anscheinend sogar direkt HTML in seinem Beitrag benutzen (wenn auch nur eine „abgespeckte“ Version).
@ZetaX: Danke für den Link. Darauf haben mich K777 und Cyrix (Cyrix wird hier auch bald auftauchen, denke ich), die schon etwas länger im Forum sind, noch nicht hingewiesen :).
[Die Antwort wurde nach Beitrag No.1 begonnen.]
Edit: Oh, ist ja interessant, gerade hat K777 geschrieben, während ich nicht hinsah. Ich hatte K777 schon in der "Mitglieder online"-Liste gesehen :).
Öh, K777, du und Kezer von uni-protokolle.de haben mich falsch verstanden, glaube ich. Das einzige, was mein damaliges Programm da herausbekam, war, dass es keine Möglichkeit für A gibt, um den Gewinn zu erzwingen, wenn A als erstes
011000000
011000000
oder
001100000
001100000
oder
000110000
000110000
setzt.
Wie du vielleicht nicht mitbekommen hast, ist meine Antwort auf Kezers Beitrag (auf Seite 1, „Nach deinem Programm verliert Anja bei allen möglichen Färbungen des Rechtecks 9x2?“) auf Seite 7 gelandet („Nö, das mit dem 9x2-Feld ist nicht sicher.“) :).
Vielleicht hast du auch nicht meinen Beitrag auf Seite 13 gesehen, in dem ich eine wesentlich optimierte Version meines Programms vorstellte und damit herausbekam, dass Anja sowohl bei 9x2 als auch bei 11x2 den Gewinn erzwingen kann :).
Weil ich annehme, dass es unsere gemeinsame Verwirrung etwas mindert, poste ich hier noch mal den aktuellen Code (mit Python-Highlighting) :).
brute.py
\sourceon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
import pprint
import cache_so as cache
"""
field = [line_1, ..., line_b]
In a line list 0 means empty, 1 means occupied.
A square [line_start, col_start, line_stop]
means the square starting at [line_start, col_start]
and going to [line_stop, col_start + (line_stop - line_start)],
where endpoints not included.
Remember that the functions change the input parameters
for speed gain.
"""
def fill_square(field, square, what):
"""Internal use only."""
width = square[2] - square[0]
for line in range(square[0], square[2]):
for col in range(square[1], square[1] + width):
field[line][col] = what
def mk_square(field, square):
"""Really fill the square on the field."""
fill_square(field, square, 1)
def rm_square(field, square):
"""Really remove the square on the field."""
fill_square(field, square, 0)
def fillable_squares(field):
"""Return list of fillable squares."""
squares = []
b = len(field)
a = len(field[0])
for line in range(b):
for col in range(a):
for width in range(1, min(a - col, b - line) + 1):
bad_field = False
for below_offset in range(width):
if field[line + width - 1][col + below_offset] == 1:
bad_field = True
break
for right_offset in range(width - 1):
if field[line + right_offset][col + width - 1] == 1:
bad_field = True
break
if bad_field:
break
squares.append([line, col, line + width])
return squares
def is_square_fillable(field, square):
"""
Return whether the square is fillable.
Shorter than invoking fillable_squares().
"""
width = square[2] - square[0]
for line in range(square[0], square[2]):
for col in range(square[1], square[1] + width):
if field[line][col]:
return False
return True
TURN_A = "turn_a"
TURN_B = "turn_b"
def can_a_win_b_on_turn(field, indicator_gen,
indicator_prepend,
a_cache, b_cache):
"""Assume that B is on turn. Check whether A can force victory."""
# Try to use cache.
if b_cache is not None:
field_tuple = tupelize_field(field)
if field_tuple in b_cache:
return b_cache[field_tuple]
fillable_b_squares = fillable_squares(field)
status = None
if indicator_gen <= 0:
new_prepend = None
for b_square_nr, b_square in enumerate(fillable_b_squares):
if indicator_gen >= 1:
new_status = int(float(b_square_nr) / len(fillable_b_squares) * 100)
if status is None or new_status > status:
status = new_status
new_prepend = indicator_prepend + str(status) + "% "
print new_prepend + "done"
mk_square(field, b_square)
can_a_now_win = (can_a_win(
field, on_turn=TURN_A,
indicator_gen=indicator_gen-1,
indicator_prepend=(None if indicator_gen <= 1 else new_prepend),
a_cache=a_cache, b_cache=b_cache)
!= [])
rm_square(field, b_square)
if not can_a_now_win:
if b_cache is not None:
b_cache[field_tuple] = False
return False
if b_cache is not None:
b_cache[field_tuple] = True
return True
def can_a_win(field, on_turn=TURN_A, optimize=True,
a_cache=None, b_cache=None, indicator_gen=0,
indicator_prepend=""):
"""
If on_turn == TURN_A, assume that A is on turn
and return the list of next steps A can take so
that A can force victory.
If on_turn == TURN_B, assume that B is on turn
and return whether A can (still) force victory.
If on_turn == TURN_A and optimize == True, then only at
most one next step will be returned (faster). Else the
whole list of next steps leading to victory will be
returned.
Remember that if the returned list is empty, there
is no way for A to force victory.
If on_turn == TURN_A and indicator_gen > 0, you will
get a percentage indicator of the amount of work that
has been done yet, until in indicator_gen'th recursion
level.
indicator_prepend is for internal use only.
For a_cache and b_cache, you may either pass None
(then no cache will be used) or an empty Cache object
from the cache module.
"""
if on_turn == TURN_A:
# Try to use cache.
if a_cache is not None:
field_tuple = tupelize_field(field)
if field_tuple in a_cache:
return a_cache[field_tuple]
fillable_a_squares = fillable_squares(field)
good_next_steps = []
status = None
for a_square_nr, a_square in enumerate(fillable_a_squares):
mk_square(field, a_square)
if indicator_gen >= 1:
new_status = int(float(a_square_nr) / len(fillable_a_squares) * 100)
if status is None or new_status > status:
status = new_status
new_prepend = indicator_prepend + str(status)+ "% "
print new_prepend + "done"
a_can_win_always = can_a_win_b_on_turn(
field, indicator_gen-1,
(None if indicator_gen <= 1 else new_prepend),
a_cache, b_cache)
rm_square(field, a_square)
if a_can_win_always:
# Step for A found. Append it to the "good steps" list.
good_next_steps.append(a_square)
if optimize:
break
if a_cache is not None:
# Cache the result.
a_cache[field_tuple] = good_next_steps[:1]
return good_next_steps
if on_turn == TURN_B:
return can_a_win_b_on_turn(field, indicator_gen,
indicator_prepend,
a_cache, b_cache)
def is_field_full(field):
for line in field:
if 0 in line:
return False
return True
def empty_field(a, b):
return [[0 for j in range(a)] for i in range(b)]
def tupelize_field(field):
return tuple([tuple(line) for line in field])
"""
Human mode means: enter 'x y width',
where x and y are the start coordinates
starting with (1, 1) from bottom-left.
E. g.:
0 1 0 1 1 1 0
1 0 0 0 1 0 1
+---+
0 0 1|0 0|1 1
| |
0 1 1|0 0|0 1
+---+
The selected square would be '4 1 2'
Python mode means: enter 'line_start col_start line_stopl',
where line_start and col_start are the first line
and col numbers of the square when thinking about it like
[line_1,
line_2,
...,
line_b]
and line_stop would be line_start + width, i. e.
the first line number that does not belong to the square.
The above example (see human mode) would then be
'2 3 4'
"""
MODE_HUMAN = "mode_human"
MODE_PYTHON = "mode_python"
"""Means who will begin."""
BEGIN_PC = "begin_pc"
BEGIN_USER = "begin_user"
def human_to_square(a, b, human):
\sourceoff
[Code für Forum zu lang, daher aufgesplittet, geht hier weiter:]
\sourceon python
x, y, width = map(int, human.split())
return [b - y - (width - 1), x - 1, b - y + 1]
def python_to_square(a, b, python):
return map(int, python.split())
def get_input_square(field, mode):
b = len(field)
a = len(field[0])
while True:
if mode == MODE_HUMAN:
square = human_to_square(a, b, raw_input("square (human) > "))
elif mode == MODE_PYTHON:
square = python_to_square(a, b, raw_input("square (python) > "))
width = square[2] - square[0]
if not (0 <= square[0] < square[2] <= b and
0 <= square[1] < square[1] + width <= a and
is_square_fillable(field, square)):
print "Illegal input. Try again."
else:
break
return square
def pprint_field(field, mode):
b = len(field)
a = len(field[0])
if mode == MODE_HUMAN:
lines = [str(b - line).rjust(3) + " | " + " ".join(map(str, field[line])) for line in range(len(field))]
dashes = "----+-" + "-" * (len(lines[0]) - 6)
bottom = " y/x| " + " ".join(map(str, range(1, a + 1)))
print "\n".join(lines) + "\n" + dashes + "\n" + bottom
elif mode == MODE_PYTHON:
lines = [str(line).rjust(3) + " | " + " ".join(map(str, field[line])) for line in range(len(field))]
dashes = "----+-" + "-" * (len(lines[0]) - 6)
bottom = " | " + " ".join(map(str, range(a)))
print "\n".join(lines) + "\n" + dashes + "\n" + bottom
def play(a, b, begin=BEGIN_PC, mode=MODE_HUMAN, optimize=True):
"""
Play!
The begin parameter determines who will begin the game.
The mode parameter determines in- and output format (see above).
The optimize parameter says whether the PC should try
to find *all* next steps for him to force victory or not.
The only advantage of optimize=False for each step the
PC makes the number of possible steps (from which he
chose one) will be displayed (just for fun).
"""
log = []
field = [[0 for a_index in range(a)] for b_index in range(b)]
pprint_field(field, mode)
print
if begin == BEGIN_USER:
user_step = get_input_square(field, mode)
log.append(["user", user_step])
mk_square(field, user_step)
pprint_field(field, mode)
print
while True:
if is_field_full(field):
print "You won."
break
pc_steps = can_a_win(field, optimize=optimize)
if pc_steps != []:
if optimize:
print "I can force victory now."
else:
print "There are now", len(pc_steps),\
"possible options for me to force victory."
pc_step = pc_steps[0]
else:
print "I cannot force victory (yet). Choosing a (deterministic) step now."
fillable_pc_squares = fillable_squares(field)
pc_step = fillable_pc_squares[0]
log.append(["pc", pc_step])
mk_square(field, pc_step)
pprint_field(field, mode)
print
if is_field_full(field):
print "I won."
break
user_step = get_input_square(field, mode)
log.append(["user", user_step])
mk_square(field, user_step)
pprint_field(field, mode)
print
print
print "Game log:"
pprint.pprint(log)
\sourceoff
cache.py
\sourceon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
class FifoNode:
def __init__(self, obj):
self.obj = obj
self.prev = None
self.next = None
def __repr__(self):
"""Just a utility."""
return ""
class Fifo:
"""
If the fifo consists of (a, b, c, d, e), then
a is the first object and e the last and
a will be removed when popping and appending
will append after e.
"""
def __init__(self):
self.first = None
self.last = None
def is_empty(self):
return (self.first is None)
def append(self, obj, obj_is_node=False):
"""
Append at the end.
You may either give an object to append (when
obj_is_node == False) or a node to be appended
(obj_is_node == True). In the latter case,
the node will be cleaned up first.
Remember *not* to append already existing nodes,
because they need the correct prev and next
attributes.
"""
if not obj_is_node:
node = FifoNode(obj)
else:
node = obj
if self.first is None:
node.prev = None
node.next = None
self.first = node
self.last = node
else:
node.prev = self.last
node.next = None
if node is not self.last:
self.last.next = node
self.last = node
def remove(self, node):
"""Remove a node."""
if node.prev is None:
# Then node is the first node.
self.pop()
elif node.next is None:
self.last = node.prev
node.prev.next = None
elif node.next is not None:
node.prev.next = node.next
node.next.prev = node.prev
def reinsert(self, node):
"""Remove the node and append it at the end."""
self.remove(node)
self.append(node, obj_is_node=True)
def pop(self):
"""Pop first element. Raise an error if impossible."""
if self.first is None:
raise IndexError("pop from empty Fifo")
obj = self.first.obj
if self.first.next is None:
self.first = None
self.last = None
else:
self.first = self.first.next
self.first.prev = None
return obj
def __repr__(self):
"""Just a utility."""
node = self.first
elems = []
while node is not None:
elems.append(node.obj)
node = node.next
return ""
class Cache:
"""
A cache for rigid data.
It saves (key: value) pairs using a fifo (if there
is no room left, remove old values). Remember
that the value associated to a key should be
deterministic, i. e. you should not pass
different values for the same key at different
times.
This is good for caching results already computed by
an algorithm that has deterministic output.
"""
def __init__(self, size=10):
self.size = size
# self.dict contains key: val pairs where
# values are lists [obj, fifo_ptr],
# where fifo_ptr is the fifo object.
self.dict = {}
self.used = 0
self.fifo = Fifo()
def __setitem__(self, key, val):
"""Set a cache item. key should be a hashable object."""
if key not in self.dict:
if self.used < self.size:
self.fifo.append(key)
self.dict[key] = [val, self.fifo.last]
self.used += 1
else:
remove_key = self.fifo.pop()
del self.dict[remove_key]
self.fifo.append(key)
self.dict[key] = [val, self.fifo.last]
# Otherwise the key already exists and we may
# assume that the value was not changed since then.
def __contains__(self, key):
"""Return whether the cache contains the given key."""
return key in self.dict
def __getitem__(self, key):
"""Get a cache item."""
dict_data = self.dict[key]
# Increase priority.
self.fifo.reinsert(dict_data[1])
return dict_data[0]
\sourceoff
und mit cythonize_both.sh kompilieren (unter Linux)
\sourceon sh
# This file is hereby placed in the PUBLIC DOMAIN.
# ABSOLUTELY NO WARRANTY.
cp brute.py brute_so.py
cp cache.py cache_so.py
cython -a brute_so.py
cython -a cache_so.py
gcc -shared -pthread -fPIC -fwrapv -O2 -Wall -fno-strict-aliasing -I/usr/include/python2.7 -o brute_so.so brute_so.c > /dev/null
gcc -shared -pthread -fPIC -fwrapv -O2 -Wall -fno-strict-aliasing -I/usr/include/python2.7 -o cache_so.so cache_so.c > /dev/null
rm brute_so.py brute_so.html brute_so.c
rm cache_so.py cache_so.html cache_so.c
\sourceoff
Übrigens für die, die Interesse daran haben: hier ist unser alter Thread :).
Edit: @K777: Ja, die Lösungen hatten wir im alten Thread auch schon gesehen (s. Seite 1) und fanden sie genau so doof. (Aber meine Lösung zu A2 ist ja fast exakt die Musterlösung, nicht?)
|
Profil
|
umlaufsatz
Senior 
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.4, eingetragen 2015-09-25
|
@"Kezer von uni-protokolle.de": Nö, unsere Lehrerin hatte mir den BWinf mal in die Hand gedrückt, ich fand die Aufgaben aber langweilig. Warst du schon mal da?
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
 | Beitrag No.5, eingetragen 2015-09-25
|
Hallo,
@umlaufsatz: Willkommen im Forum. Ich habe vor einiger Zeit auch über eine BWM-Diskussion hierher gefunden.
Was Aufgabe 1 angeht: Wenn die lange Seite des Rechtecks gerade (und die kurze ungerade) ist, gewinnt Anja (auch wieder durch Symmetrie, indem sie ein Quadrat, dessen Seitenlänge 1 kürzer als die kurze Seite ist, in die Mitte legt).
Wenn die lange Seite ungerade und genau eins größer ist als die kurze Seite, gewinnt Anja, indem sie ein maximales Quadrat benutzt.
Viele Grüße
Zvz
[Die Antwort wurde nach Beitrag No.3 begonnen.]
|
Profil
|
Kezer
Senior 
Dabei seit: 04.10.2013
Mitteilungen: 1862
 | Beitrag No.6, eingetragen 2015-09-25
|
\quoteon(2015-09-25 19:45 - umlaufsatz in Beitrag No. 4)
@"Kezer von uni-protokolle.de": Nö, unsere Lehrerin hatte mir den BWinf mal in die Hand gedrückt, ich fand die Aufgaben aber langweilig. Warst du schon mal da?
\quoteoff
Erstmal zu diesem "Ich hätte dein Programm falsch verstanden", ich glaube, das war wieder wegen dem Forum, ich hab nämlich nichts explizites zu deinem Programm geschrieben, kam wahrscheinlich von K7.
Und joa, ich hab letztes Jahr mit einem Freund teilgenommen. Und ja, deine Lösung zur A2 ist fast genau die Lösung vom BWM, nicht schlecht! ;)
@K7 Wenn man A 4 geometrisch macht, ist sie ganz schön, alles andere läuft wohl leider auf analytischen Geometrie raus :P
Vielleicht schafft gibt es hier ja irgendwelche Ideen zur allgemeinen A1, zu der der Aufgabensteller wohl keine Lösung gefunden hat, Zvz hat schließlich schon damit angefangen!
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.7, eingetragen 2015-09-25
|
@Kezer: Ach, du bist ja auch schon hier seit Langem im Forum registriert :) ? Und, stimmt, K7 hat das gesagt :). Habe mich geirrt. Danke und sorry. Ich meinte das „Nach deinem Programm verliert Anja bei allen möglichen Färbungen des Rechtecks 9x2?“ von K7 auf Seite 1 :). Du bist eher der Programmierfreak, der mein Programm gut versteht. Habt ihr beim BWinf Preise abgeräumt :)?
Ist es eigentlich OK, wenn ich so große Mengen Code hier direkt poste?
@Zvz: Naja, im alten Thread hatten wir schon alle Fälle
(a, b gerade), (a, b ungerade), (a gerade, b ungerade, a > b) gehabt und genau so gelöst wie du. Fehlt also nur noch (a ungerade, b gerade, a > b). Der Fall a = b + 1 mit b gerade ist übrigens auch der erste Fall, für den ich die Aufgabe lösen konnte (bevor der Brief mit der 2. Version der Aufgaben kam). Gelöst habe ich auch diesen Fall so wie du :).
Ich kann ja erst mal mit meinem Programm schauen, ob für (a, b) = (13, 2) A den Gewinn erzwingen kann :).
|
Profil
|
Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1862
| Beitrag No.8, eingetragen 2015-09-25
|
\quoteon(2015-09-25 21:33 - umlaufsatz in Beitrag No. 7)
@Kezer: Du bist eher der Programmierfreak, der mein Programm gut versteht. Habt ihr beim BWinf Preise abgeräumt :)?
\quoteoff
Neee, so gut bin ich nicht beim Programmieren, da bist du viel besser und mein Kumpel auch und jop, wir waren da sogar ganz gut ^^
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.9, eingetragen 2015-09-26
|
Jetzt habe ich noch einen Durchbruch bei A1 erzielt: Bei (a, b) = (13, 2) kann A nicht den Gewinn erzwingen.
Habe mein Programm mit einem Cache von 700.000 Zellen eineinhalb Stunden laufen lassen (RAM voll + unbenutzte Pages in 200 MiB Swap ausgelagert). Es war zwar erst zu 63% mit der Ausführung fertig, aber mit Symmetrieüberlegungen konnte ich leicht feststellen, dass die 63% schon reichten: Als 1. Züge von A hatte mein Programm die Quadrate
\codeon python
fillable_squares(empty_field(13, 2))[:24] ==
[[0, 0, 1], [0, 0, 2], [0, 1, 1], [0, 1, 2], [0, 2, 1], [0, 2, 2],
[0, 3, 1], [0, 3, 2], [0, 4, 1], [0, 4, 2], [0, 5, 1], [0, 5, 2],
[0, 6, 1], [0, 6, 2], [0, 7, 1], [0, 7, 2], [0, 8, 1], [0, 8, 2],
[0, 9, 1], [0, 9, 2], [0, 10, 1], [0, 10, 2], [0, 11, 1], [0, 11, 2]]
\codeoff
schon ausprobiert ($63\% \cdot 38 = 23.94 \approx 24$). Das sind alle Quadrate der Breite 1 auf der oberen Zeile des Spielfelds (außer dem ganz rechts oben, das aber redundant ist) und alle Quadrate der Breite 2 auf dem Spielfeld. Und diese reichen aus für eine Betrachtung, ob A den Gewinn erzwingen kann.
Die restlichen Möglichkeiten wären übrigens
\codeon python
fillable_squares(empty_field(13, 2))[24:] ==
[[0, 12, 1], [1, 0, 2], [1, 1, 2], [1, 2, 2], [1, 3, 2], [1, 4, 2],
[1, 5, 2], [1, 6, 2], [1, 7, 2], [1, 8, 2], [1, 9, 2], [1, 10, 2],
[1, 11, 2], [1, 12, 2]]
\codeoff
gewesen, die sind aber alle redundant.
Hoffe, ich habe keinen Bug im Programm :).
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.10, eingetragen 2015-09-26
|
Hallo,
ich bin die kleinen 2xn Rechtecke mal von Hand durchgegangen (das geht schneller, als man denkt).
Für n=2,3,6,7,8 kann A sowohl den eigenen Sieg als auch die eigene Niederlage erzwingen.
Für n=4,5 kann A den eigenen Sieg erzwingen und B die eigene Niederlage.
Für n=9 kann B sowohl Sieg als auch Niederlage erzwingen.
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.11, eingetragen 2015-09-26
|
@Zetavonzwei: $\zeta (2) = \sum\limits_{n = 1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}$, oder :) ?
Glaubst du, dass bei (a, b) = (9, 2) wirklich B den Gewinn erzwingen kann, wenn A anfängt? Dann wäre ja mein Programm falsch (kann sein, kann sein). Wollen wir mal hier im Forum spielen? Ich benutze mein Programm und du machst das mutig per Hand :) ?
Ich bin A und du B und du zeigst mir, dass du den Gewinn erzwingen kannst. Ich (=A) fange an (1 = besetztes Feld, 0 = leeres Feld):
100000000
000000000
Jetzt bist du dran :).
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
|  Beitrag No.12, eingetragen 2015-09-26
|
Hallo,
Ich glaube, ich habe einen Paritätswechsel übersehen.
Aber ich probiere trotzdem mal
100000110
000000110
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.13, eingetragen 2015-09-26
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.14, eingetragen 2015-09-26
|
Hallo,
ja, stimmt. Jetzt kannst du als A sowohl den eigenen Sieg als auch die eigene Niederlage erzwingen. Meine 5 ist daher auch falsch (daher kommt der Fehler). A kann hier beides erzwingen (nicht nur einen Sieg).
Ich korrigiere also folgendermaßen:
Für n=2,3,5,6,7,8,9 kann A sowohl Sieg als auch Niederlage erzwingen.
Für n=4 kann A nur einen Sieg erzwingen.
Viele Grüße
Zvz
|
Profil
|
Ex_Senior
| Beitrag No.15, eingetragen 2015-09-26
|
Wow! :)
Da war die Kleinigkeit ("und der andere Fall geht analog"), die hier vielleicht angenommen wurde, aber nicht gilt, und damit zu der notwendigen Änderung des Aufgabentextes führte, doch Gold wert:
Die Aufgaben des BWM sollen auch über die eigentliche Lösung zum Nachdenken und Beschäftigen mit dem Thema anregen.
Und DAS hat diese Geschichte ganz offenbar bewirkt! :)
Ihr könnt ja mal weiter probieren und evtl. Vermutungen anstellen, wie sich das Spiel im noch ungeklärten Fall verhält.
(Wenn ich irgendwann mal wieder Zeit finde, schaue ich mir auch mal den Code an. Das Konzept der Dynamischen Programmierung [aka Speichern von schon Errechneten Zwischenergebnissen anstatt sie ständig neu zu berechnen] ist ja auch schon dabei als Nebenprodukt entdeckt worden. :) )
Viel Spaß weiterhin!
Cyrix
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
|  Beitrag No.16, eingetragen 2015-09-29
|
In den letzten Tagen habe ich versucht, die Caches noch effizienter zu machen. Sie hatten ja schon eine Heuristik, dass die Einträge als erste rausfliegen, die schon am längsten drin sind und in Zwischenzeit am wenigsten gelesen wurden (also weniger „relevant“ sind).
Nun versuchte ich, einen Cache mit mehreren Sub-Caches aufzubauen, wobei jeder Eintrag, der in den Cache eingefügt wird, eine Prioritätszahl hat, die festlegt, in welchen Sub-Cache er eingetragen wird. Damit kann man dann sozusagen erzwingen, dass Einträge mit höherer Priorität länger im Cache bleiben als ohne Sub-Cache-Konzept. Es liegt nahe, den berechneten Werten für die Spielfelder mit wenigen ausgefüllten Kästchen eine höhere Priorität zu geben, da deren Neuberechnung viel mehr Zeit beansprucht als bei Spielfeldern mit vielen schon ausgefüllten Kästchen. Das habe ich dann auch so implementiert. Aber es gibt leider keinen Geschwindigkeitsvorteil (sondern wird etwa 1.5-mal so langsam). Vielleicht hilft es erst bei größeren Feldgrößen (a, b) :).
Mich würde zum Beispiel noch brennend interessieren, ob A auf (a, b) = (7, 4) den Gewinn erzwingen kann. Kann das jemand ohne PC lösen?
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.17, eingetragen 2015-09-29
|
Hmm, hattet ihr schon gesehen, dass in der Lösung zu A1 am Ende steht: „Mir ist derzeit kein allgemeines Kriterium bekannt, nach dem entschieden werden kann, wer den Gewinn erzwingen kann, wenn a < b, a gerade, b ungerade.“ :) ? Dann scheint es ja doch wirklich nicht einfach zu sein. Wollen wir Andrew Wiles mal fragen ;) ?
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.18, eingetragen 2015-09-29
|
Hallo,
eine kleine Beobachtung: Wenn wir das Spielfeld als einen Graphen ansehen (Knoten=Kästchen, Kanten=Verbindungen zwischen Kästchen), dann entfernen Spieler abwechselnd zusammenhängende Mengen von Knoten (samt ihren Kanten).
Den Sieg kann genau der Spieler erzwingen, der als erstes erreichen kann, dass nach seinem Zug jeder (graphentheoretische) Isomorphietyp von Zusammenhangskomponenten geradzahlig oft vorkommt.(*)
Kurze Beweisskizze:
"<="Wenn dies der Fall ist, kann der Spieler stets den vorausgehenden Zug des Gegners kopieren und verliert daher nicht.
"=>" Wenn ein Spieler gewinnt, dann gibt es keine Zusammenhangskomponente mehr, d.h. jede ZSHK kommt genau 0 mal (gerade oft) vor (d.h. spätestens dann ist die Bedingung erfüllt).
Insbesondere könnte man das Spiel verallgemeinern auf beliebige Graphen und andere Typen von ZSHK. (Was natürlich die Suche nach Invarianten verkompliziert). Derzeit sind wir "nur" bei Graphen, in denen alle Knoten höchstens Grad 4 haben.
Viele Grüße
Zvz
PS: (*) lässt sich noch etwas "abschwächen", wenn es geradzahlig viele Knoten gibt, die sich nur durch Einerquadrate überdecken lassen. Diese Knoten kann man dann ignorieren.
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.19, eingetragen 2015-09-29
|
Oh, das klingt ja nett (bin aber kein Graphentheorieexperte und brauche deshalb noch etwas Zeit, um deine Idee nachzuvollziehen). Ob das für den Computer taugt? Es braucht zum Beispiel auch Rechenzeit, um zu überprüfen, ob alle Kästchen auf dem Feld sich nur durch Einheitsquadrate überdecken lassen …
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.20, eingetragen 2015-09-29
|
Hallo,
die Einschränkung weiter unten wird nicht viel bringen (Da geht es im Wesentlichen um Einerzeilen)
Was die Beobachtung angeht:
Ohne Graphentheorie heißt das, wenn es jeden Typ von Gebiet gerade oft gibt (dabei ist ein Gebiet eine zusammenhängende Menge von unbesetzten Feldern):
0010001100111000
0010001100111000
In diesem Feld gewinnt der Spieler, der als zweites dran ist (also diese Situation herbeigeführt hat), weil es zwei 2x2 und zwei 2x3 Blöcke gibt.
000000011
010011001
000101001
Auch in diesem Feld gewinnt der zweite Spieler, diesmal nach dem "abgeschwächten" Kriterium (Ich markiere die "Einerblöcke"):
xx00xxx11
x10011001
xxx1x1001
Was die Argumentation angeht:
-Wenn A auf eines der x setzt, dann setzt B auf ein anderes x und führt damit wieder eine Situation mit einer geraden Anzahl x und einer geraden Anzahl gleicher Gebiete herbei
-Wenn A einen anderen Zug macht (also auf eine der Nullen setzt), dann führt B den gleichen Zug im korresponierenden Gebiet aus.
An einem einfachereren Beispiel:
00011001
00011000
00111000
Zug von A:
11011001
11011000
00111000
Zug von B:
11011001
11011110
00111110
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.21, eingetragen 2015-09-29
|
Ja, danke :) ! Hab's jetzt sofort verstanden. Stimmt. Ist eine Art Verallgemeinerung unserer Lösung zu A1 bei (a, b gerade).
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.22, eingetragen 2015-10-01
|
Neuigkeiten vom Python-Programm: Zuerst hatte ich gar nicht so darüber nachgedacht, wie man Zvz's Bemerkung mit den 1x1-Kästchen implementieren könnte. Ich dachte erst nur an den allgemeinen Fall, den Zvz geschildert hatte (d. h. nur durch 1x1-Quadrate überdeckbare Kästchen aus der Betrachtung wegzulassen). Dann aber kam mir ein Einfall: Nur den Fall abkürzen, bei dem alle Kästchen auf dem Spielfeld nur durch 1x1-Quadrate überdeckbar sind – und die Implementierung war ziemlich einfach, es brauchte de facto lediglich folgenden Extra-Code:
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
# Try a shortcut :).
shortcut = True
for square in fillable_a_squares:
if square[2] - square[0] > 1:
shortcut = False
break
if shortcut:
if len(fillable_a_squares) % 2 == 1:
# A can force victory.
if optimize == OPT_RET:
if a_cache is not None:
a_cache[field_tuple, generation] = fillable_a_squares[:1]
return fillable_a_squares
elif optimize == OPT_SHORT:
if a_cache is not None:
a_cache[field_tuple, generation] = fillable_a_squares[:1]
return fillable_a_squares[:1]
else:
# A cannot force victory.
# The optimize param has no effect here.
if a_cache is not None:
a_cache[field_tuple, generation] = []
return []
\codeoff
Damit habe ich jetzt bei (a, b) = (13, 2) etwa eine sechsmal größere Geschwindigkeit. Danke, Zvz :) !
Edit: Jetzt habe ich auch den Rest von Zvz's Idee mit den 1x1-Quadraten implementiert (weil ich dachte, wenn allein schon der Spezialfall oben schon alles sechsmal schneller macht, dann wird das jetzt noch viel schneller). Es wurde auch schneller, wieder etwa 5 Mal. Der Fall (a, b) = (13, 2) läuft jetzt nicht mehr in 1.5 Stunden, sondern in 3 Minuten :).
Ich habe damit gleich mein Programm an (a, b) = (7, 4) drangesetzt, aber nach 1.5 Stunden ist er noch immer bei grob berechnet 0.023% der gesamten Berechnung ("0% 0% 46% done" zeigt er an). Zvz, ich brauche noch ein paar Optimierungen ;) !
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.23, eingetragen 2015-10-02
|
Hallo,
schön, dass die Beobachtung was gebracht hat.
Was weitere Ideen angeht:
Bei den "Einerkästen" kommt es gar nicht auf die genaue Anzahl, sondern nur auf die Parität an.
Etwas genauer:
Sei S ein Spielfeld, als nächstes Spieler A am Zug und M eine "Einerkästenmenge" (die unverbunden mit S ist [damit eine Bildung neuer größerer Blöcke ausgeschlossen ist]).
Dann gilt:
a) Falls M gerade viele Elemente hat, gewinnt in $M\cup S$ genau der Spieler, der in $S$ gewinnt.
b) Falls M ungerade viele Elemente hat und B eine Siegstrategie auf S hat, dann hat A eine Siegstrategie auf $S\cup M$
c) Falls M ungerade viele Elemente hat und jeder erste Zug von A auf S in eine Situation führt, in der A noch den Sieg erzwingen kann, gewinnt B.*
Beweis:
a) Fall 1: B hat eine Gewinnstrategie auf S. Setzt A in S, dann macht B den nächsten Schritt dieser Gewinnstrategie. Setzt A in M, dann setzt auch B in M und hat somit wieder eine Situation mit geradem M und eigener Gewinnstrategie herbeigeführt. Spätestens, wenn M leer ist, kann A dort nicht mehr setzen und B gewinnt mit seiner Gewinnstrategie in S.
Fall 2: A hat eine Gewinnstrategie auf S. Dann macht A den ersten Zug dieser Strategie und hat damit das Problem auf Fall 1 reduziert.
b) A setzt in M. Damit ist jetzt B am Zug und findet eine Situation, in der der zweite Spieler eine Siegstrategie auf S hat und in M gerade viele Felder. Folglich hat jetzt (nach a) A eine Siegstrategie auf $S\cup M$
c)Setzt A auf M, dann hat jetzt offenbar B eine Siegstrategie (nach a). Andernfalls setzt B auf M. Dann hat B ebenfalls (nach a) eine Siegstrategie.
*Für den Fall "A hat Siegstrategie und M ist ungerade" ist mir noch kein allgemeineres Resultat eingefallen. Allerdings ist auch hier die genaue Größe von M unwichtig, denn sobald der erste Platz in M belegt ist, liegt die Situation von a) vor.
viele Grüße
Zvz
Zusatz: Teil a) gilt auch für beliebig große Felder: Ist $S$ ein Spielfeld und sind $M$ und $N$ isomorphe* Felder, die voneinander und von $S$ getrennt sind, dann hat auf $S\cup M\cup N$ genau der Spieler eine Siegstrategie, der auf $S$ eine Siegstrategie hat.
Der Beweis geht analog zu oben.
*isomorphe Felder: Vorerst in Graphentheoretischer Hinsicht, insbesondere sind Felder isomorph, die sich durch Drehen und Spiegeln ineinander überführen lassen. Man kann das noch etwas abschwächen, aber dafür muss ich noch eine Formulierung finden.
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.24, eingetragen 2015-10-03
|
Hallo Zvz. a) und b) hatte ich schon implementiert (und damit die Geschwindigkeitssteigerungen aus dem vorigen Post erzielt, relevanter Code siehe unten). c) ist dann nicht ganz so einfach zu implementieren wie a) und b); und ich versuche ja sowieso schon einen Kompromiss zwischen Optimierung und Code-Länge zu machen ;).
Ich befürchte, dass das rein mathematische Überlegen bei dieser Aufgabe doch noch ein bisschen länger braucht, bis es zum Ziel führt … Daher danke vor allem für eure (auch zukünftigen) Ideen, die sich leicht implementieren lassen und einen hohen Geschwindigkeitsvorteil bringen :D.
Code-Patches willkommen :) !
Was ich allerdings schon noch implementieren könnte, wäre ein Symmetrietest, der dann nachschaut, ob eine gespiegelte Variante schon im Cache ist (oder nur die notwendigen Quadrate von fillable_squares() ausprobiert). Ob das etwas bringt?
Der relevante Code für die a)- und b)-Optimierungen von Zvz:
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
def is_standalone(field, position):
"""
Check whether the given 1x1 square is standalone.
'standalone' means that there is no fillable square
of width >= 2 that the given 1x1 square is part of.
"""
a = len(field[0])
b = len(field)
line, col = position
# FOR TESTING.
if field[line][col] == 1:
raise IndexError("Bug")
# Bottom-left.
if (line <= b - 2 and col >= 1 and
is_square_fillable(field, [line, col - 1, line + 2])):
return False
# Top-right.
if (line >= 1 and col <= a - 2 and
is_square_fillable(field, [line - 1, col, line + 1])):
return False
# Top-left.
if (line >= 1 and col >= 1 and
is_square_fillable(field, [line - 1, col - 1, line + 1])):
return False
# Bottom-right.
if (line <= b - 2 and col <= a - 2 and
is_square_fillable(field, [line, col, line + 2])):
return False
return True
def get_standalones(field):
"""
Get the standalone 1x1 squares.
They will be returned as [[line, col], ...].
See is_standalone() for more information.
"""
standalones = []
for line in range(len(field)):
for col in range(len(field[0])):
if (field[line][col] == 0 and
is_standalone(field, [line, col])):
standalones.append([line, col])
return standalones
\codeoff
und weiter unten:
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
standalones = get_standalones(field)
if standalones != []:
for standalone in standalones:
field[standalone[0]][standalone[1]] = 1
a_can_now_win = can_a_win_int(
field, TURN_A, sub_optimize, a_cache,
b_cache, generation, indicator_gen,
indicator_prepend)
for standalone in standalones:
field[standalone[0]][standalone[1]] = 0
if len(standalones) % 2 == 0:
# A can still force victory,
# if A could force victory in the
# simplified field. Choose a
# step from the simplified field now.
# If there are no steps there, we cannot
# win either.
step = a_can_now_win[:1]
else:
if a_can_now_win == []:
# A can now clearly win. Just
# choose a simple step from the
# standalone squares.
step = [standalones[0]]
else:
# See long comment above. It is
# not clear who will win.
step = None
if step is not None:
if a_cache is not None:
a_cache[field_tuple, generation] = step
return step
# Else, step is None and we have to work
# through the full routine.
\codeoff
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.25, eingetragen 2015-10-05
|
Ich habe jetzt auch die Symmetrietests implementiert. Ergebnis: nichts. Code wird etwas (ca. 10%) langsamer. Ich dachte auch: Na ja, vielleicht hilft jetzt meine Cache-Implementierung mit den Prioritätscaches, denn dann kann das Programm am Ende abkürzen, weil die wichtigen gespiegelten/rotierten Ergebnisse noch im Prio-1-Cache stehen. Sie stehen zwar auch im Prio-1-Cache und dadurch sind mehr als 50% aller Rechnungen auf (a, b) = (13, 2) überflüssig, aber die Ausführung der letzten 63 Prozent hatte ich ja sowieso nicht gemessen (und die letzten $ \approx 60\% $ habe ich auch schon immer vernachlässigt, weil die nur aus Spielfeldern bestehen, bei denen eine symmetrischen Variante schon getestet wurde).
Zvz, ich brauche meeeeeeeehr Optimierungen ;).
Relevanter Code zu den Symmetrietests:
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
TRAFO_FLIP_H = 0
TRAFO_FLIP_V = 1
TRAFO_ROT = 2
def transform_field(field, trafo):
"""
Return a new transformed field (as lists).
trafo should be one of TRAFO_FLIP_H, TRAFO_FLIP_V and
TRAFO_ROT.
"""
a = len(field[0])
b = len(field)
if trafo == TRAFO_FLIP_H:
return [[field[b - line - 1][col] for col in range(a)]
for line in range(b)]
if trafo == TRAFO_FLIP_V:
return [[field[line][a - col - 1] for col in range(a)]
for line in range(b)]
if trafo == TRAFO_ROT:
return [[field[b - line - 1][a - col - 1] for col in range(a)]
for line in range(b)]
def transform_square_inv(square, trafo, field):
"""
Return a new inverse-transformed square.
trafo should be one of TRAFO_FLIP_H, TRAFO_FLIP_V
and TRAFO_ROT. The field only needs to be passed
so that length and width are clear.
The square will be inversely transformed by the
given transformation, i. e. the square that,
transformed by the given trafo, equals the given
arg square will be returned.
However, as long as trafo is one of TRAFO_FLIP_H,
TRAFO_FLIP_V or TRAFO_ROT, this does not make
any difference and is just like applying the
given trafo to the square (instead of
trafo^(-1)), as trafo is an involution.
"""
first_line = square[0]
first_col = square[1]
last_line = square[2]
width = last_line - first_line
a = len(field[0])
b = len(field)
if trafo == TRAFO_FLIP_H:
return [b - last_line, first_col, b - last_line + width]
if trafo == TRAFO_FLIP_V:
return [first_line, a - (first_col + width), last_line]
if trafo == TRAFO_ROT:
return [b - last_line, a - (first_col + width), b - last_line + width]
\codeoff
und weiter unten in can_a_win_int():
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
# Test whether a symmetric version is in the cache.
if optimize == OPT_SHORT and a_cache is not None:
for transformation in [TRAFO_FLIP_H,
TRAFO_FLIP_V,
TRAFO_ROT]:
transformed = tupelize_field(
transform_field(field, transformation))
if transformed in a_cache:
can_win = a_cache[transformed]
if can_win == []:
a_cache[field_tuple, generation] = []
return []
else:
step = transform_square_inv(
can_win[0], transformation, field)
a_cache[field_tuple, generation] = [step]
return [step]
\codeoff
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.26, eingetragen 2015-10-05
|
Hallo,
ich habe eine Verallgemeinerung des 1-Block-Lemmas gefunden.
Um mir (auch bei evtl. weiteren Beobachtungen) Notation zu sparen, eine kurze Definition:
Eine Spielsituation heiße $A^+$-Feld ($B^+$-Feld), wenn der Spieler am Zug (nächste Spieler) den Sieg erzwingen kann. Ein Feld heiße $A^-$-Feld ($B^-$-Feld), wenn der Spieler am Zug (nächste Spieler) die Niederlage erzwingen kann.
Jetzt die Beobachtung:
Satz ($B^+$-Felder):
Es sei $S$ ein Feld und $M$ ein davon getrenntes Feld.
Dann gilt:
a) Ist $M$ ein $B^+$-Feld, so ist $S\cup M$ genau dann ein $A^+$-Feld, wenn $S$ ein $A^+$-Feld ist.
b) Ist $M$ ein $A^+$-Feld und $S$ ein $B^+$-Feld, so ist $S\cup M$ ein $A^+$-Feld
c) Sind $M$ und $S$ beide $A^+$-Felder, so müssen o.B.d.A. auf $S\cup M$ nur solche Züge betrachtet werden, die diesen Zustand erhalten. Gibt es keinen solchen Zug, ist die Situation insgesamt $B^+$.
Beweis:
a)$\Rightarrow$: Es sei $S$ ein $B^+$-Feld. Setzt A auf $S$, so macht B den nächsten Zug seiner Siegstrategie auf $S$ und somit liegen vor dem nächsten Zug von A wieder zwei $B^+$-Felder vor. Setzt A auf $M$, so macht B den nächsten Zug seiner Siegstrategie auf $M$ und es liegen ebenfalls vor dem nächsten Zug von A zwei $B^+$-Felder vor.
Da durch die Züge die Felder verkleinert werden und B stets ziehen kann, gewinnt B.
$\Leftarrow$: Es sei $S$ ein $A^+$-Feld. A beginnt mit dem ersten Zug seiner Strategie auf $S$. Dadurch liegen vor dem Zug von B zwei $B^+$-Felder vor. Folglich ist das Feld vor dem Zug von B nach ($\Rightarrow$) ein $B^+$-Feld. Folglich ist die Situation zu Beginn ein $A^+$-Feld.
b) Folgt aus a)($\Leftarrow$) mit vertauschten Rollen von $M$ und $S$.
c) Da A nur in eines der beiden Felder setzen kann, kommen als folgende Spielsituation nur die Möglichkeiten $S$ ist $A^+$ und $M$ ist $A^+$, $S$ ist $A^+$ und $M$ ist $B^+$, $S$ ist $B^+$ und $M$ ist $A^+$ in Frage. Die beiden letztgenannten Fälle sind nach a) und b) $A^+$-Felder.
Folglich gewinnt bei ersten Zügen, die diese Situationen herbeiführen, B.
Also beginnt jede Siegstrategie von A mit einem Zug, der die $A^+$,$A^+$-Situation aufrecht erhält.
Viele Grüße
Zvz
PS: Da ich es schon mehrfach "intuitiv" benutzt habe:
Es seien $S$, $M$ und $G$ Felder mit $S\cup M=G$. $S$ und $M$ heißen "getrennt" (in $G$), wenn für jedes nxn-Quadrat Q gilt:
$Q\cap S\neq \emptyset\Rightarrow Q\cap M=\emptyset$.
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.27, eingetragen 2015-10-05
|
Wow, das klingt doch schon mal so, als ob ich das implementieren könnte (Beweise habe ich überprüft und keinen Fehler gefunden, gut so!). Damit kann man zwar nicht direkt bei gegebenen Feldern S und M, wobei S ein $ X^+ $- und M ein $ Y^+ $-Feld ist ($ X, Y \in \{A, B\} $), entscheiden, ob $ S \cup M $ nun $ A^+ $ oder $ B^+ $ ist, sondern im Fall c) noch ein bisschen rechnen. Aber das muss man ja sowieso, denn am Anfang sind ja noch gar keine getrennten Felder vorhanden ;).
Da kann ich ja meinen Symmetriealgorithmus wegschmeißen :).
Ich weiß auch schon einen Trennungsalgorithmus :) (d. h. einen, der zu gegebenem Feld die getrennten Einzelteile liefert).
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.28, eingetragen 2015-10-05
|
Hallo,
na das klingt doch vielversprechend.
Ich bin mal gespannt, ob sich dadurch eine Verbesserung erzielen lässt (bzw. wie stark diese ist).
(Der Haupteffekt meiner Beobachtung wird vermutlich sein, dass du alle $B^+$-Felder ignorieren kannst)
Viele Grüße
Zvz
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.29, eingetragen 2015-10-06
|
Hallo,
leider scheint das Ende der Fahnenstange mit diesem Ansatz bereits erreicht zu sein:
Die Felder $(2,2),(3,2),(8,2)$ sind alle $A^+$-Felder, die gleichzeitig $A^-$-Felder sind. Allerdings ist $(2,2)\cup(2,2)$ $B^+$ und $(3,2)\cup (8,2)$ $A^+$ (letzteres, weil sonst A in (13,2) durch eine Zerlegung in diese beiden Teile (Setzen eines 2x2-Blocks) einen Sieg erzwingen könnte).
Das ist auch nicht weiter verwunderlich, denn eigentlich mache ich gar keine Aussage über dieses spezielle Spiel. Der Beweis bleibt richtig, wenn man den Satz wie folgt verallgemeinert:
Satz ((Disjunkte) Vereinigung von Spielen): Es seien $S$ und $M$ zwei Spiele, in denen jeweils derjenige Spieler gewinnt, der den letzten Zug macht. Das Spiel $S\cup M$ sei so definiert, dass ein Zug in $S\cup M$ darin besteht, entweder einen Zug in $M$ oder einen Zug in $S$ auszuführen, und derjenige Spieler verliert, der nicht mehr ziehen kann.
Dann gilt:
a) Ist $M$ ein $B^+$-Feld, dann ist $S\cup M$ genau dann $A^+$, wenn $S$ ein $A^+$-Feld ist.
b) Ist $M$ ein $A^+$-Feld und $S$ ein $B^+$-Feld, dann ist $S\cup M$ ein $A^+$-Feld.
c) Sind $M,S$ $A^+$-Felder, so ist eine so allgemeine Aussage über $S\cup M$ nicht möglich. Allerdings kann man o.B.d.A. annehmen, dass jede Siegstrategie mit einem Schritt beginnt, der wieder in eine $A^+A^+$-Situation führt.
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.30, eingetragen 2015-10-06
|
Hmm, stimmt das auch, wenn die Felder nicht getrennt sind? Die Formulierung ein Zug, der darin besteht, entweder einen Zug in $ M $ oder einen Zug in $ S $ auszuführen ist mir nicht ganz klar. Du meinst ein Zug, der darin besteht, ein Quadrat auf $ M $ oder $ S $ zu färben, das eine leere Schnittmenge mit $ S $ bzw. $ M $ hat, oder?
Denn deine Formulierung liest sich für mich wie ein Zug, der darin besteht, ein Quadrat zu färben, das entweder vollständig auf $ M $ liegt oder vollständig auf $ S $ (das Quadrat kann in diesem Fall nämlich eine nichtleere Schnittmenge mit $ S $ bzw. $ M $ haben). Für meine Implementierung (ist noch nicht so weit) ist das aber egal, denn ich betrachte ja sowieso nur getrennte Felder; und dort sind beide Formulierungen äquivalent :).
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.31, eingetragen 2015-10-06
|
Hallo,
"Spiel" war in einem allgemeineren Sinn gemeint (nämlich so, dass es sich um zwei beliebige Spiele (d.h. die insbesondere nicht zwingend auf Karos gespielt werden) handelt, die nichts miteinander zu tun haben).
Ein wenig Recherche hat dann ergeben, dass es ein ähnliches Resultat bereits gibt ( hier).
Ich versuche, das demnächst mal in eine verständliche Kurzfassung zu bringen.
Jedenfalls ist der relevante Punkt, dass man bei jedem neutralen Spiel (wie diesem) rekursiv eine Zahl berechnen kann, die angibt, wer gewinnen kann.
Für den Fall der (2,n)-Quadrate hat das den Effekt, dass ein äußerst simpler Algorithmus bereits ausreicht:
\sourceon python
#Berechnet eine Liste von allen Spielwerten von 0 bis n
def listnums(n):
x=[]
for i in range(n+1):
w=[]
#Spielfeldzerfall in ein bis drei kleinere Rechtecke
for j in range(i-1):
#Erster Schritt: A setzt 1x1 auf (1,j+1)
w.append((x[j]^1)^x[i-j-1])
#Erster Schritt: A setzt das Quadrat (1,j+1),(1,j+2),(2,j+1),(2,j+2)
w.append((x[j]^x[i-j-2]))
#Suche die kleinste nichtnegative ganze Zahl, die nicht in w vorkommt
#Wahrscheinlich gibts da noch bessere Methoden
w.sort()
s=0
for j in w:
if s==j:
s=s+1
x.append(s)
return x
\sourceoff
Jedenfalls erhält man so für die (2,n)-Rechtecke für n=1,...,100 als die Werte, bei denen B gewinnt:
0, 1, 13, 25, 37, 49, 61, 73, 85, 97
Es scheint so, als ob in diesem Spezialfall B den Sieg genau dann erzwingen kann, wenn n=0 oder $n\equiv 1\mod 12$.
Einen Beweis dafür habe ich aber bisher noch nicht.
Für (m,n)-Rechtecke mit m,n>2 zerfällt das Spiel leider nicht sofort.
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.32, eingetragen 2015-10-07
|
Oh, krass! So eine Idee mit einem entzweiteilenden 1x1-Quadrat hatte ich mir zwar auch schon überlegt, allerdings nicht zu Ende gedacht, weil Teil c) deines Lemmas immer noch ein bisschen Rechnen braucht (und nicht nur Rekursion), was hier wohl nicht nötig ist … :)
Das können wir / kannst du ja dem Karl Fegert vom BWM schreiben :).
Durch deinen Link blicke ich noch nicht durch, aber dass Spieltheorie so nett sein kann, wusste ich auch noch nicht. Und dass du Python kannst :) !
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.33, eingetragen 2015-10-07
|
Hallo,
naja, für den kleinen Algorithmus reichts dann doch...
Stimmt, der Wiki-Artikel ist nicht besonders gut verständlich. Vielleicht ist das besser (Relevant sind die Abschnitte 4 und 5).
Ich fasse mal die wesentlichen Punkte für das Spiel zusammen:
Es sei Z die Menge aller Spielpositionen und zu $z\in Z$ sei $F(z)$ die Menge aller möglichen Nachfolgepositionen. Dann definiert man eine Funktion $g:Z\to\mathbb{N}_0$ (die Sprague-Grundy-Funktion) durch $g(z)=min\left{n\geq 0:n\neq g(y)\ \text{für alle}\ y\in F(z)\right}$.
Für diese Funktion gilt:
a) Wenn der Spieler am Zug nicht mehr ziehen kann (d.h. B gewinnt), dann ist g(z)=0 (weil $F(z)=\emptyset$.
b) Wenn g(z)=0, dann gibt es keinen Zug $z\mapsto z'$ mit g(z')=0 (sonst wäre g(z)=g(z')).
c) Wenn $g(z)\neq 0$, dann gibt es einen Zug $z\mapsto z'$ mit g(z')=0 (andernfalls wäre g(z) nicht minimal).
Daraus folgt: A kann genau dann den Sieg erzwingen, wenn $g(z)\neq 0$ gilt. (Die Strategie besteht darin, (wenn möglich) immer den Zug in c) anzuwenden).
Satz (Summe von Spielen): Sind X und Y zwei Spiele mit Sprague-Grundy-Funktionen $g_X$ und $g_Y$ und "Spielzugfunktionen" $F_X$ und $F_Y$, so hat das Spiel $Z:=X\times Y$, mit $F(x,y)=F_X(x)\times\{y\}\cup \{x\}\times F_Y(y)$*, die Sprague-Grundy-Funktion $g$ mit $g(x,y)=g_X(x)\oplus g_Y(y)$. Dabei ist $\oplus$ durch die bitweise XOR-Operation in der Binärdarstellung definiert (also $2\oplus 3=10_2\oplus 11_2=01_2=1$.)
Beweis: Wir müssen die Eigenschaften der Sprague-Grundy-Funktion nachrechnen, also
a) Falls es einen Zug $(x,y)\mapsto (x',y')$ gibt, dann ist $g(x,y)\neq g(x',y')$ und
b) $g(x,y)$ ist minimal, d.h. aus $0\leq a
|
Profil
|
Ex_Senior
| Beitrag No.34, eingetragen 2015-10-07
|
Wenn man mit diesem Hilfsmittel die in Beitrag No. 31 aufgestellte Vermutung für 2 x n - Felder beweisen könnte, wäre das tatsächlich etwas, was man Karl Fegert schicken kann, damit er es in die Musterlösung aufnimmt (das Ergebnis; der Beweis passt thematisch nicht ganz). :)
Cyrix
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.35, eingetragen 2015-10-07
|
Hallo,
Wie es aussieht könnte die Vermutung sich erhärten:
Ich habe mal die ersten Spielzahlen in Spalten nach Zwölferrest aufgeteilt (erste Spalte Rest 0, letzte Rest 11).
[0, 0, 2, 2, 1, 4, 3, 3, 1, 4, 2, 6]
[5, 0, 2, 7, 1, 4, 3, 3, 1, 4, 7, 7]
[5, 0, 2, 8, 4, 4, 6, 3, 1, 8, 7, 7]
[5, 0, 2, 2, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 4, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 7, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
Danach scheinen die Spielzahlen periodisch zu werden (wobei die Periode genau die letzte Zeile ist). Zeigen könnte man das, indem man systematisch die Aufteilungen nach Zwölferresten durchgeht und die resultierende Spielzahl berechnet.
Ein Feld der Größe (2,m) mit $m\equiv k \mod 12$ zerfällt dann (modulo 12) durch den ersten Schritt von A in 2xs Blöcke der Größen $l$ und $k-l-2$ oder in 2xs Blöcke der Größen $l$ und $k-l-1$ und einen 1x1-Block.
Wenn man davon ausgeht, dass $l$ die kleinere Zahl ist, kann man für $k-l-1$ bzw. $k-l-2$ den entsprechenden Wert aus der Periode nehmen [Weil dann das Restfeld "genügend groß" ist (d.h. >72,d.h. man muss bis n=144 die Zeile überprüfen; das habe ich bereits getan)] und muss nur für $l$ ggf. eine Fallunterscheidung machen.
Folglich müssen (wenn ich Recht habe), nur noch 216 Werte (bzw. die daraus resultierenden Spielwerte) berechnet werden.
Das scheint nur noch eine Fleiß- oder Programmieraufgabe zu sein.
KORREKTUR: Das braucht gar nicht mehr zu erfolgen. In meinem Algorithmus wird das in der Zeile n=144 bis n=155 bereits überprüft (schließlich geht der Algorithmus hier bereits die möglichen Fälle in dieser Aufteilung durch).
Wenn mein Algorithmus korrekt ist (und das sollte er sein nach dem, was ich oben geschrieben habe), dann genügt es, die Fälle bis n=155 zu testen. Ich lasse also den Algorithmus laufen und erhalte (in 12er Zeilen aufgeteilt) das Ergebnis
[0, 0, 2, 2, 1, 4, 3, 3, 1, 4, 2, 6]
[5, 0, 2, 7, 1, 4, 3, 3, 1, 4, 7, 7]
[5, 0, 2, 8, 4, 4, 6, 3, 1, 8, 7, 7]
[5, 0, 2, 2, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 4, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 7, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
[5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7]
Folglich werden die Spielzahlen für n>72 periodisch und insbesondere kann B genau dann in (2,n) den Sieg erzwingen, wenn $n\equiv 1 \mod 12$ ist. (Sollte ich mich bei der Bedingung "genügend groß" etwas vertan haben, dann macht das nichts, denn auch die nächsten Zeilen passen noch)
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.36, eingetragen 2015-10-09
|
Zvz, ich habe jetzt aus deinem Satz über die disjunkte Vereinigung von Spielen a) und b) implementiert, c) habe ich wieder weggelassen. Ergebnis: wesentlich langsamer. Liegt aber wohl auch daran, dass ich deine Optimierungen nur zum Teil optimiert implementiert habe :). Code schicke ich irgendwann nach (die can_a_win-Funktion heißt jetzt who_wins_zvz :), ich habe sie vollständig neu implementiert).
Wenn ich nun statt a), b) und c) die Sprague-Grundy-Funktion benutze, dann ist das im Wesentlichen nichts anders (also nicht von anderer Komplexitätsklasse) als a) und b) zu implementieren und mit ein bisschen Magie (von der gleichen Komplexitätsklasse, mithilfe von Sprague-Grundy) auch den Fall c), scheint mir. Dann dürfte es also etwas effizienter sein, als mein Programm es jetzt gerade ist, aber ich glaube, die große Geschwindigkeitsbremse liegt im Moment noch beim Trennungsalgorithmus :).
Übrigens: Toll, dass du ein Gesetz für (a, b) = (n, 2) herausgefunden hast! Ich komme leider gerade nicht dazu, das zu kontrollieren :).
|
Profil
|
Zetavonzwei
Senior
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
| Beitrag No.37, eingetragen 2015-10-10
|
Hallo,
dass die Sprague-Grundy-Funktion in den größeren Fällen nicht viel bringt, dachte ich mir schon, schließlich gibt es da sehr viele Fälle des "Nicht-Zerfallens" (und um die SGF auszurechnen braucht man dann ja alle Nachfolgezüge).
Für (2,x) hat sie allerdings tatsächlich einen Beweis möglich gemacht.
Viele Grüße
Zvz
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.38, eingetragen 2015-10-10
|
Ich habe jetzt folgenden Code mit den "getrennten 1x1-Kästchen" wieder hinzugefügt (nachdem ich ihn natürlich gelöscht hatte, weil er als Spezialfall in deinem Satz vorkommt – aber mein Trennungsalgorithmus ist ja so langsam, dass es hier Sinn machte, den Spezialfall wieder explizit einzuprogrammieren):
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
standalones = get_standalones(field)
num_removable = len(standalones) - len(standalones) % 2
if num_removable > 0:
standalones_to_be_removed = standalones[:num_removable]
for standalone in standalones_to_be_removed:
field[standalone[0]][standalone[1]] = 1
result = who_wins_zvz_int(field, cache, False)
for standalone in standalones_to_be_removed:
field[standalone[0]][standalone[1]] = 0
cache[field_tuple] = result
return result
\codeoff
Damit dauert
\codeon python
who_wins_zvz_int(empty_field(13, 2), cache.Cache(1000000), True)
\codeoff
nur 8 Sekunden, gegenüber den ca. 4 Minuten von vorher ist das nun 30 Mal so schnell :). Ich sende den vollständigen Code später nach.
|
Profil
|
umlaufsatz
Senior
Dabei seit: 25.09.2015
Mitteilungen: 823
| Beitrag No.39, eingetragen 2015-10-10
|
Oh mein Gott, sind deine Optimierungen fantastisch :) !
Ich habe jetzt in meine komplett neu geschriebenen Funktionen wieder den Status-Indikator und das "optimize"-Argument eingebaut (und verbessert). Und dann (erst dann, denn dazu brauche ich einen Status-Indikator) habe ich Folgendes gemacht:
\codeon python
>>> who_wins(empty_field(7, 4), cache.Cache(1000000), OPT_ONE, 3)
0% done
0% 0% done
0% 0% 0% done
0% 0% 1% done
…
0% 1% 20% done
0% 3% done
0% 5% done
1% done
(0, [[0, 0, 2]])
\codeoff
Das hat nur 3 Minuten gedauert! Und wir wissen jetzt, dass A bei (a, b) = (7, 4) den Gewinn erzwingen kann!
Da würde ich ja fast sagen, ich implementiere mal die Sprague-Grundy-Funktion :). Muss aber auch nicht sein (siehe meinen vorletzten Post).
Und ich könnte mal (a, b) = (9, 4) versuchen.
Hier der vollständige Code des Programms: (Soll ich ihn irgendwo auslagern?)
Das Spielen gegen den Computer funktioniert übrigens jetzt noch nicht mit der neuen Implementierung. Repariere ich noch.
brute.py:
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
import pprint
import cache_so as cache
"""
field = [line_1, ..., line_b]
In a line list 0 means empty, 1 means occupied.
A square [line_start, col_start, line_stop]
means the square starting at [line_start, col_start]
and going to [line_stop, col_start + (line_stop - line_start)],
where endpoints not included.
Remember that the functions change the input parameters
for speed gain.
"""
def fill_square(square, field, what):
"""Internal use only."""
width = square[2] - square[0]
for line in range(square[0], square[2]):
for col in range(square[1], square[1] + width):
field[line][col] = what
def mk_square(square, field):
"""Really fill the square on the field."""
fill_square(square, field, 1)
def rm_square(square, field):
"""Really remove the square on the field."""
fill_square(square, field, 0)
def get_fillable_squares(field):
"""Return list of fillable squares."""
squares = []
b = len(field)
a = len(field[0])
for line in range(b):
for col in range(a):
for width in range(1, min(a - col, b - line) + 1):
bad_field = False
for below_offset in range(width):
if field[line + width - 1][col + below_offset] == 1:
bad_field = True
break
for right_offset in range(width - 1):
if field[line + right_offset][col + width - 1] == 1:
bad_field = True
break
if bad_field:
break
squares.append([line, col, line + width])
return squares
def is_square_fillable(square, field):
"""
Return whether the square is fillable.
Shorter than invoking get_fillable_squares().
"""
width = square[2] - square[0]
for line in range(square[0], square[2]):
for col in range(square[1], square[1] + width):
if field[line][col]:
return False
return True
def is_square_in_field(square, field):
"""Check whether the square is on the field or exceeds it."""
a = len(field[0])
b = len(field)
return (0 <= square[0] < square[2] <= b and
0 <= square[1] < square[1] + (square[2] - square[0]) <= a)
def is_pos_in_square(pos, square):
"""Check whether the position pos == [line, col] is in the square."""
width = square[2] - square[0]
return (square[0] <= pos[0] < square[2] and
square[1] <= pos[1] < square[1] + width)
def is_field_full(field):
"""
Check whether the field is full.
If it is full, return True. Else return an empty
[line, col] square.
"""
a = len(field[0])
b = len(field)
for line in range(b):
for col in range(a):
if field[line][col] == 0:
return [line, col]
return True
def get_edges(square):
"""
Get the [line, col] positions on the edges.
Some positions may occur multiple times.
"""
edges = []
width = square[2] - square[0]
for line in range(square[0], square[2]):
edges.append([line, square[1]])
edges.append([line, square[1] + width - 1])
for col in range(square[1] + 1, square[1] + width - 1):
edges.append([square[0], col])
edges.append([square[2] - 1, col])
return edges
def get_square_positions(square):
"""Get the [line, col] positions of the points in the square."""
pos = []
width = square[2] - square[0]
for line in range(square[0], square[2]):
for col in range(square[1], square[1] + width):
pos.append([line, col])
return pos
def split_comp_off(field, fillable_squares=None):
"""
Split a component comp off and return (new_field, comp).
This function assumes that field is not empty.
For the definition of a component, see
get_components().
If you pass a fillable_squares list of squares
so that all fillable squares are contained in it
(but not neccessarily all squares in
fillable_squares must actually be fillable), it
will be used for optimization.
"""
is_full = is_field_full(field)
if is_full == True:
raise BugError
if fillable_squares is None:
fillable_squares = get_fillable_squares(field)
# Work on a copy.
field = [line[:] for line in field]
fifo = cache.Fifo()
fifo.append(is_full)
# comp contains all squares that have been added
# to the component.
comp = [[is_full[0], is_full[1], is_full[0] + 1]]
comp_min_line = is_full[0]
comp_max_line = is_full[0] + 1
comp_min_col = is_full[1]
comp_max_col = is_full[1] + 1
# Put all new found positions into the fifo and
# analyze them one after another.
# Keep track of what has already been inserted
# into the fifo.
already_in_fifo = set()
while not fifo.is_empty():
position = fifo.pop()
already_in_fifo.add(tuple(position))
for square in fillable_squares:
if not is_pos_in_square(position, square):
continue
if not is_square_fillable(square, field):
continue
comp.append(square)
for edge_pos in get_edges(square):
edge_pos_tuple = tuple(edge_pos)
if edge_pos_tuple not in already_in_fifo:
already_in_fifo.add(edge_pos_tuple)
fifo.append(edge_pos)
comp_min_line = min(comp_min_line, square[0])
comp_max_line = max(comp_max_line, square[2])
comp_min_col = min(comp_min_col, square[1])
comp_max_col = max(comp_max_col, square[1] +
(square[2] - square[0]))
# We will optimize and make our "small" square
# indeed smaller in size than the main field
# if possible.
comp_field = [[1 for col in range(comp_max_col - comp_min_col)]
for line in range(comp_max_line - comp_min_line)]
for square in comp:
transl_square = [
square[0] - comp_min_line,
square[1] - comp_min_col,
square[2] - comp_min_line]
# Make a component out of our comp squares.
rm_square(transl_square, comp_field)
# Update the main field for the next component.
mk_square(square, field)
return field, comp_field
def get_components(field):
\codeoff
(kurze Unterbrechung, weil Code zu lang für Editor)
\codeon python
"""
Get the connected components of the field.
A part S of the field is called connected if for any
two points in S there exists a 'path' of 1x1
squares x_1, ..., x_n in S so that for all i
both x_i and x_(i + 1) are contained in a square
Q, where Q is fully contained in S.
A (connected) component of the field means a
connected part of the field that no 1x1 squares
can be added to without making it non-connected,
i. e. it is a 'maximal' component w. r. t.
connectedness.
"""
fillable_squares = get_fillable_squares(field)
components = []
while True:
is_full = is_field_full(field)
if is_full == True:
break
field, comp = split_comp_off(field, fillable_squares)
components.append(comp)
return components
def is_standalone(field, position):
"""
Check whether the given 1x1 square is standalone.
'standalone' means that there is no fillable square
of width >= 2 that the given 1x1 square is part of.
"""
a = len(field[0])
b = len(field)
line, col = position
# Bottom-left.
if (line <= b - 2 and col >= 1 and
is_square_fillable([line, col - 1, line + 2], field)):
return False
# Top-right.
if (line >= 1 and col <= a - 2 and
is_square_fillable([line - 1, col, line + 1], field)):
return False
# Top-left.
if (line >= 1 and col >= 1 and
is_square_fillable([line - 1, col - 1, line + 1], field)):
return False
# Bottom-right.
if (line <= b - 2 and col <= a - 2 and
is_square_fillable([line, col, line + 2], field)):
return False
return True
def get_standalones(field):
"""
Get the standalone 1x1 squares.
They will be returned as [[line, col], ...].
See is_standalone() for more information.
"""
standalones = []
for line in range(len(field)):
for col in range(len(field[0])):
if (field[line][col] == 0 and
is_standalone(field, [line, col])):
standalones.append([line, col])
return standalones
VICTORY_A = 0
VICTORY_B = 1
# OPT_ALL means: Return *all* A steps to force victory.
# OPT_ONE means: Return at most *one* A step.
# OPT_NONE means: Return *no* A step.
# In any case however, the maximum number of allowed steps
# will be returned if possible (all, 1 or 0). Of course,
# also always VICTORY_A or VICTORY_B will be returned.
OPT_ALL = 0
OPT_ONE = 1
OPT_NONE = 2
def status_msg(done, whole, gen_prep):
"""
Print a status message and return the sub-gen_prep value.
For done, pass an int.
The whole argument may be a list or an int. In
the list case its length len(whole) will be used
for the message.
The gen_prep argument must be a list or tuple
(indicator_generation, indicator_prep).
Then (indicator_generation - 1, new_indicator_prep)
will be returned.
"""
gen, prep = gen_prep
if gen == 0:
return 0, None
if not isinstance(whole, int):
whole = len(whole)
sub_prep = prep + str(int(float(done) / whole * 100)) + "% "
print sub_prep + "done"
return gen - 1, sub_prep
def who_wins(field, cache=None, optimize=OPT_ONE,
indicator_gen=0):
"""
Check who wins on the given field.
In the simplest case, just the type of the field,
i. e. VICTORY_A or VICTORY_B will be returned.
There are some additional features here that
return additional values:
If optimize == OPT_ALL, then *all* possible
steps for A to force victory will be returned.
If optimize == OPT_ONE, then *one* possible
step for A to force victory will be returned (if
victory is impossible, return []).
If optimize == OPT_NONE, then *no* possible
step for A to force victory will be returned,
i. e. only VICTORY_A or VICTORY_B.
You will get a percentage indicator of the
amount of work that has been done yet, until in
indicator_gen'th recursion level.
For the cache argument, you may pass an (empty)
Cache object from the cache module.
"""
return who_wins_zvz_int(
field, cache, optimize, (indicator_gen, ""))
def who_wins_nozvz_int(field, cache, optimize, gen_prep):
"""Internal function."""
# This is an optimized version of who_wins_zvz_int()
# for the case that the field is known to be connected
# or has to be handled as a connected field where no
# Zvz Optimization is possible.
# However, both who_wins_nozvz_int() and
# who_wins_zvz_int() are interchangeable in their
# general behavior.
square_found = False
good_squares = []
fillable_squares = get_fillable_squares(field)
for square_nr in range(len(fillable_squares)):
square = fillable_squares[square_nr]
mk_square(square, field)
typ = who_wins_zvz_int(
field, cache, OPT_NONE, status_msg(
square_nr, fillable_squares, gen_prep))
rm_square(square, field)
if typ == VICTORY_B:
good_squares.append(square)
if optimize == OPT_ONE or optimize == OPT_NONE:
break
if len(good_squares) > 0:
if optimize == OPT_ALL or optimize == OPT_ONE:
return VICTORY_A, good_squares
else:
return VICTORY_A
else:
if optimize == OPT_ALL or optimize == OPT_ONE:
return VICTORY_B, []
else:
return VICTORY_B
def who_wins_zvz_int(field, cache, optimize, gen_prep):
"""Internal function."""
# The cache will always only contain VICTORY_A
# or VICTORY_B.
if optimize != OPT_NONE:
return who_wins_nozvz_int(
field, cache, optimize, gen_prep)
# Now, we can optimize using Hard-core Zvz :).
field_tuple = tupelize_field(field)
if field_tuple in cache:
return cache[field_tuple]
standalones = get_standalones(field)
num_removable = len(standalones) - len(standalones) % 2
if num_removable > 0:
standalones_to_be_removed = standalones[:num_removable]
for standalone in standalones_to_be_removed:
field[standalone[0]][standalone[1]] = 1
result = who_wins_zvz_int(
field, cache, OPT_NONE, gen_prep)
for standalone in standalones_to_be_removed:
field[standalone[0]][standalone[1]] = 0
cache[field_tuple] = result
return result
fillable_squares = get_fillable_squares(field)
if len(fillable_squares) == 0:
# Empty field.
cache[field_tuple] = VICTORY_B
return VICTORY_B
new_field, comp = split_comp_off(field, fillable_squares)
if is_field_full(new_field) == True:
nozvz_result = who_wins_nozvz_int(
field, cache, OPT_NONE, gen_prep)
cache[field_tuple] = nozvz_result
return nozvz_result
else:
# Apply optimization.
typ_1 = who_wins_zvz_int(
new_field, cache, OPT_NONE, gen_prep)
typ_2 = who_wins_nozvz_int(
comp, cache, OPT_NONE, gen_prep)
if typ_1 == VICTORY_A and typ_2 == VICTORY_A:
# Cannot optimize easily well here.
result = who_wins_nozvz_int(
field, cache, OPT_NONE, gen_prep)
elif typ_1 == VICTORY_A and typ_2 == VICTORY_B:
result = VICTORY_A
elif typ_1 == VICTORY_B and typ_2 == VICTORY_A:
result = VICTORY_A
elif typ_1 == VICTORY_B and typ_2 == VICTORY_B:
result = VICTORY_B
cache[field_tuple] = result
return result
def empty_field(a, b):
\codeoff
(kurze Unterbrechung, weil Code zu lang für Editor)
\codeon python
return [[0 for j in range(a)] for i in range(b)]
def tupelize_field(field):
return tuple([tuple(line) for line in field])
"""
Human mode means: enter 'x y width',
where x and y are the start coordinates
starting with (1, 1) from bottom-left.
E. g.:
0 1 0 1 1 1 0
1 0 0 0 1 0 1
+---+
0 0 1|0 0|1 1
| |
0 1 1|0 0|0 1
+---+
The selected square would be '4 1 2'
Python mode means: enter 'line_start col_start line_stopl',
where line_start and col_start are the first line
and col numbers of the square when thinking about it like
[line_1,
line_2,
...,
line_b]
and line_stop would be line_start + width, i. e.
the first line number that does not belong to the square.
The above example (see human mode) would then be
'2 3 4'
"""
MODE_HUMAN = "mode_human"
MODE_PYTHON = "mode_python"
# Means who will begin.
BEGIN_PC = "begin_pc"
BEGIN_USER = "begin_user"
def human_to_square(a, b, human):
x, y, width = map(int, human.split())
return [b - y - (width - 1), x - 1, b - y + 1]
def square_to_human(a, b, square):
x = square[1] + 1
width = square[2] - square[0]
y = - square[0] + b - (width - 1)
return str(x) + " " + str(y) + " " + str(width)
def python_to_square(a, b, python):
return map(int, python.split())
def square_to_python(a, b, square):
return str(square[0]) + " " + str(square[1]) + " " + str(square[2])
def input_to_square(a, b, mode, inp):
if mode == MODE_HUMAN:
return human_to_square(a, b, inp)
if mode == MODE_PYTHON:
return python_to_square(a, b, inp)
def square_to_output(a, b, mode, out):
if mode == MODE_HUMAN:
return square_to_human(a, b, out)
if mode == MODE_PYTHON:
return square_to_python(a, b, out)
SUPPORT_PC = "support_pc"
SUPPORT_PC_FORCE = "support_pc_force"
SUPPORT_HINT = "support_hint"
def get_input_square(field, mode):
b = len(field)
a = len(field[0])
while True:
inp = raw_input("square (" + mode + ") > ")
if inp in ["", "y", "you", "pc", "try", "t"]:
return SUPPORT_PC
if inp in ["pcf", "force", "!"]:
return SUPPORT_PC_FORCE
if inp in ["h", "hint", "help", "opt", "tip"]:
return SUPPORT_HINT
square = input_to_square(a, b, mode, inp)
width = square[2] - square[0]
if not (0 <= square[0] < square[2] <= b and
0 <= square[1] < square[1] + width <= a and
is_square_fillable(square, field)):
print "Illegal input. Try again."
else:
break
return square
def pprint_field(field, mode):
b = len(field)
a = len(field[0])
if mode == MODE_HUMAN:
lines = [str(b - line).rjust(3) + " | " + " ".join(map(str, field[line])) for line in range(len(field))]
dashes = "----+-" + "-" * (len(lines[0]) - 6)
bottom = " y/x| " + " ".join(map(str, range(1, a + 1)))
print "\n".join(lines) + "\n" + dashes + "\n" + bottom
elif mode == MODE_PYTHON:
lines = [str(line).rjust(3) + " | " + " ".join(map(str, field[line])) for line in range(len(field))]
dashes = "----+-" + "-" * (len(lines[0]) - 6)
bottom = " | " + " ".join(map(str, range(a)))
print "\n".join(lines) + "\n" + dashes + "\n" + bottom
def get_user_square(field, mode, optimize, a_cache, b_cache):
"""Please the user until he knows what he wants to do. Return a square."""
a = len(field[0])
b = len(field)
while True:
user_step = get_input_square(field, mode)
if user_step in [SUPPORT_PC, SUPPORT_PC_FORCE]:
user_steps = can_a_win(field, optimize=optimize,
a_cache=a_cache,
b_cache=b_cache)
if user_steps != []:
print "You can force victory now. Taking over your turn."
user_step = user_steps[0]
# Solution found.
break
else:
if user_step == SUPPORT_PC:
print "You cannot force victory. Do what you like."
elif user_step == SUPPORT_PC_FORCE:
print "You cannot force victory. Taking over your turn."
user_step = get_fillable_squares(field)[0]
break
elif user_step == SUPPORT_HINT:
user_steps = can_a_win(field, optimize=optimize,
a_cache=a_cache,
b_cache=b_cache)
print "Using any of the following steps you can force victory:"
if user_steps == []:
print "(none)"
for user_step in user_steps:
print square_to_output(a, b, mode, user_step)
else:
break
return user_step
def play(a, b, begin=BEGIN_PC, mode=MODE_HUMAN, optimize=True,
a_cache=None, b_cache=None):
"""
Play!
The begin parameter determines who will begin the game.
The mode parameter determines in- and output format (see above).
The optimize parameter says whether the PC should try
to find *all* next steps for him to force victory or not.
The only advantage of optimize=False for each step the
PC makes the number of possible steps (from which he
chose one) will be displayed (just for fun).
"""
log = [["size", [a, b]]]
field = empty_field(a, b)
pprint_field(field, mode)
print
if begin == BEGIN_USER:
user_step = get_user_square(field, mode, optimize,
a_cache, b_cache)
log.append(["user", user_step])
mk_square(user_step, field)
pprint_field(field, mode)
print
while True:
if is_field_full(field) == True:
print "You won."
break
pc_steps = can_a_win(field, optimize=optimize,
a_cache=a_cache, b_cache=b_cache)
if pc_steps != []:
if optimize or (a_cache is not None):
print "I can force victory now."
pc_step = pc_steps[0]
else:
if len(pc_steps) == 1:
print "There is now one possible option for me"\
"to force victory."
pc_step = pc_steps[0]
else:
print "There are now", len(pc_steps),\
"possible options for me to force victory."
print "Which one do you want me to choose?"
for step_nr, step in enumerate(pc_steps):
print str(step_nr + 1) + ": " + square_to_output(a, b, mode, step)
while True:
chosen = int(raw_input("Choose > "))
if 1 <= chosen <= len(pc_steps):
break
print "Illegal input. Try again."
pc_step = pc_steps[chosen - 1]
else:
print "I cannot force victory (yet). Choosing a (deterministic) step now."
fillable_pc_squares = get_fillable_squares(field)
pc_step = fillable_pc_squares[0]
log.append(["pc", pc_step])
mk_square(pc_step, field)
pprint_field(field, mode)
print
if is_field_full(field) == True:
print "I won."
break
user_step = get_user_square(field, mode, optimize,
a_cache, b_cache)
log.append(["user", user_step])
mk_square(user_step, field)
pprint_field(field, mode)
print
print
print "Game log:"
pprint.pprint(log)
\codeoff
cache.py:
\codeon python
## This file is hereby placed in the PUBLIC DOMAIN.
## ABSOLUTELY NO WARRANTY.
class FifoNode:
def __init__(self, obj):
self.obj = obj
self.prev = None
self.next = None
def __repr__(self):
"""Just a utility."""
return ""
class Fifo:
"""
If the fifo consists of (a, b, c, d, e), then
a is the first object and e the last and
a will be removed when popping and appending
will append after e.
"""
def __init__(self):
self.first = None
self.last = None
def is_empty(self):
return (self.first is None)
def append(self, obj, obj_is_node=False):
"""
Append at the end.
You may either give an object to append (when
obj_is_node == False) or a node to be appended
(obj_is_node == True). In the latter case,
the node will be cleaned up first.
Remember *not* to append already existing nodes,
because they need the correct prev and next
attributes.
"""
if not obj_is_node:
node = FifoNode(obj)
else:
node = obj
if self.first is None:
node.prev = None
node.next = None
self.first = node
self.last = node
else:
node.prev = self.last
node.next = None
if node is not self.last:
self.last.next = node
self.last = node
def remove(self, node):
"""Remove a node."""
if node.prev is None:
# Then node is the first node.
self.pop()
elif node.next is None:
self.last = node.prev
node.prev.next = None
elif node.next is not None:
node.prev.next = node.next
node.next.prev = node.prev
def reinsert(self, node):
"""Remove the node and append it at the end."""
self.remove(node)
self.append(node, obj_is_node=True)
def pop(self):
"""Pop first element. Raise an error if impossible."""
if self.first is None:
raise IndexError("pop from empty Fifo")
obj = self.first.obj
if self.first.next is None:
self.first = None
self.last = None
else:
self.first = self.first.next
self.first.prev = None
return obj
def __repr__(self):
"""Just a utility."""
node = self.first
elems = []
while node is not None:
elems.append(node.obj)
node = node.next
return ""
class Cache:
"""
A cache for rigid data.
It saves (key: value) pairs using a fifo (if there
is no room left, remove old values). Remember
that the value associated to a key should be
deterministic, i. e. you should not pass
different values for the same key at different
times.
This is good for caching results already computed by
an algorithm that has deterministic output.
Set a value: c[key] = val
Get a value: c[key]
Check whether contains: key in c
"""
def __init__(self, size=50000):
self.size = size
# self.dict contains key: val pairs where
# values are lists [obj, fifo_ptr],
# where fifo_ptr is the fifo object.
self.dict = {}
self.used = 0
self.fifo = Fifo()
def __setitem__(self, key, val):
"""Set a cache item. key should be a hashable object."""
if key not in self.dict:
if self.used < self.size:
self.fifo.append(key)
self.dict[key] = [val, self.fifo.last]
self.used += 1
else:
remove_key = self.fifo.pop()
del self.dict[remove_key]
self.fifo.append(key)
self.dict[key] = [val, self.fifo.last]
# Otherwise the key already exists and we may
# assume that the value was not changed since then.
def __contains__(self, key):
"""Return whether the cache contains the given key."""
return key in self.dict
def __getitem__(self, key):
"""Get a cache item."""
dict_data = self.dict[key]
# Increase priority.
self.fifo.reinsert(dict_data[1])
return dict_data[0]
# Remember speed gain by caches :).
PRIO_IGN = 0
PRIO_ERR = 1
PRIO_DFLT = 2
class PrioCache:
"""
A cache for rigid data with priority categories.
This cache saves (key: value) pairs in priority
categories.
Set a value: c[key, prio] = val
Get a value: c[key]
Check whether contains: key in c
For further documentation see the Cache class.
The reason why this PrioCache exists is that
Cache does heuristic priority handling based on
the frequency of how often a key is called (via
__getitem__). This is very useful as long as the
values which truly *have* to be cached are cached.
However, imagine the case where you are in the
middle of a computation of a whole recursive
tree of function calls and want to dynamically
cache already computed values. Your cache may
now contain most of the ramified parts of the
tree, but all values from the higher parts of
the tree have been removed, as they were not
needed for computation for a long time.
While actually the highest parts of the tree would
take longest to compute again, the Cache could
not figure that out with its simple heuristics.
You have to tell it what contents of the cache
have higher priority and shall be kept even when
they are not needed immediately. And that is why
there is this PrioCache.
"""
def __init__(self, sizes, default_prio=None,
on_bad_prio=PRIO_ERR):
"""
Make the cache.
sizes[prio] should be the size of the cache of
items that have prio priority. sizes itself
may either be a list or a dict.
If default_prio != None, then insert (key: val)
pairs into the cache associated with this
prio, when in a __setitem__ call no prio is
given (e. g. c[key] = val instead of c[key,
prio] = val).
If on_bad_prio == PRIO_IGN, then ignore __setitem__
calls with a non-existent priority.
If on_bad_prio == PRIO_ERR, raise an error when
a __setitem__ call with a bad prio happens.
If on_bad_prio == PRIO_DFLT, put the (key: val)
pair into the default cache (remember to provide
a default_prio).
"""
if isinstance(sizes, list):
sizes = dict(enumerate(sizes))
self.sizes = sizes
self.caches = {prio: Cache(self.sizes[prio]) for
prio in self.sizes}
self.default_prio = default_prio
self.bad_prio = on_bad_prio
# FOR OPTIMIZATION.
self.hits = {prio: 0 for prio in self.sizes}
self.misses = 0
def __setitem__(self, key, val):
"""Set a value with given priority."""
# Maybe the pair already appears in a different
# cache (prio). But this does not matter.
if not isinstance(key, tuple):
key = [key, self.default_prio]
elif key[1] not in self.caches:
if self.bad_prio == PRIO_ERR:
raise IndexError("priority " + repr(key[1]) +
" does not exist")
elif self.bad_prio == PRIO_DFLT:
key = [key[0], self.default_prio]
elif self.bad_prio == PRIO_IGN:
return
self.caches[key[1]][key[0]] = val
def __contains__(self, key):
"""Return whether the cache contains key."""
for prio in self.caches:
if key in self.caches[prio]:
self.hits[prio] += 1
return True
self.misses += 1
return False
def __getitem__(self, key):
"""Get a value."""
for cache in self.caches.values():
if key in cache:
return cache[key]
raise KeyError(key)
\codeoff
cythonize_both.sh:
\codeon sh
# This file is hereby placed in the PUBLIC DOMAIN.
# ABSOLUTELY NO WARRANTY.
cp brute.py brute_so.py
cp cache.py cache_so.py
cython -a brute_so.py
cython -a cache_so.py
gcc -shared -pthread -fPIC -fwrapv -O2 -Wall -fno-strict-aliasing -I/usr/include/python2.7 -o brute_so.so brute_so.c > /dev/null
gcc -shared -pthread -fPIC -fwrapv -O2 -Wall -fno-strict-aliasing -I/usr/include/python2.7 -o cache_so.so cache_so.c > /dev/null
rm brute_so.py brute_so.html brute_so.c
rm cache_so.py cache_so.html cache_so.c
\codeoff
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
