Inhoud
In dit artikel gaan we kijken naar drie verschillende onderwerpen. Allereerst kijken we naar het spelletje 15-en dat met 2 personen kan worden gespeeld of met 1 persoon tegen de computer. Daarna kijken we naar het beroemde spelletje Boter-Kaas-en-Eieren (BKE) en gaan we op zoek naar een goede strategie. Tot slot kijken we naar het magisch vierkant. Dit is een vierkant van 3×3 met een bijzondere eigenschap. Zo op het oog nogal een ratjetoe van totaal verschillende onderwerpen. Het spel 15-en gaat als volgt, we gaan even ervan uit dat 2 personen tegen elkaar spelen: Leg op tafel 9 kaartjes neer met daarop respectievelijk de getallen 1 tot en met 9. Om de beurt mag een speler 1 van de kaartjes op tafel pakken. Wanneer een speler met 3 van zijn kaartjes de som van 15 kan maken heeft deze gewonnen. Voorbeeld: Speler 1 kiest kaartje met nummer 7 erop (in ’t kort: S1G7), Speler 1 heeft nu 3 kaarten met de waardes: 7, 3 en 8. Hiermee kan hij /zij geen 15 maken. S2G1 Speler 2 heeft nu 3 kaarten met de waardes: 5, 4 en 1 en hiermee kan hij/zij geen 15 maken. S1G2 Speler 1 kan nog steeds geen 15 maken met 3 van zijn/haar 4 kaarten. S2G9 Speler 2 heeft nu de kaarten: 4, 5, 1 en 9 en kan nu wel 15 maken. Namelijk met de kaarten 4, 1 en 9 want 4+1+9=15. Speler 2 heeft dus gewonnen! Met het onderstaande Python programma kun je dit spel tegen de computer spelen. Python 15-en Permutaties en combinaties In de Python code wordt gebruik gemaakt van een functie die combinaties berekent. Maar wat is ook al weer het verschil tussen combinaties en permutaties? Voor beiden geldt dat je kijkt op hoeveel en op welke manier je k elementen uit een verzameling van n elementen haalt. Voor de combinatie geldt dat de volgorde er niet toe doet. De formule voor de combinatie luidt: De formule voor de permutatie luidt: Laten we eens kijken op hoeveel manieren je 3 elementen uit een verzameling van 4 elementen kunt halen: Het aantal combinaties is: Het aantal permutaties is: Voorbeeld: Stel we hebben de verzameling {1, 2, 3, 4}. Als we vervolgens eens kijken naar de verzameling {1, 2, 3} en gaan hiervan de permutaties bekijken (dat zijn er 6) dan krijgen we: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} en {3, 2, 1}. En ik had al 4 combinaties en er zijn dus per combinatie 6 permutaties. Dat betekent dat er 4×6 permutaties van onze startverzameling zijn: De vraag is nu: Is er een winnende strategie? Dit spel is overbekend maar voor diegenen die het toch niet kennen even een korte uitleg: Boter-Kaas-en-Eieren wordt gespeeld op een 3×3 bord tussen 2 spelers. De speler die begint speelt met een X en de andere speler speelt met een O. Per beurt mag een speler zijn/haar symbool op een leeg vak plaatsen. De eerste die een horizontale, verticale of diagonale rij met zij/haar symbool heeft gemaakt heeft gewonnen. Een spel kan er als volgt uitzien: Met het onderstaande Python programma kun je dit spel tegen de computer spelen. Python BKE En ook hier luidt de vraag: Is er een winnende strategie? Een magisch vierkant is een vierkant gevuld met getallen waarbij (op z’n minst) de sommen van de rijen, kolommen en (hoofd-)diagonalen gelijk zijn. Voorbeeld: In bovenstaand 4×4-vierkant zijn de getallen 1 t/m 16 zodanig ingevuld dat de som van de rijen, kolommen en hoofddiagonalen allemaal gelijk zijn, namelijk 34. De moeder van alle magische vierkanten, HET magisch vierkant, is een vierkant van 3×3 waar de getallen 1 t/m 9 zodanig zijn ingevuld dat de som van de rijen, kolommen en diagonalen gelijk zijn, namelijk 15: Om een 3×3 magisch vierkant te maken kun je gebruik maken van de volgende methode: Op die manier vul je, als het ware, de diagonalen. Deze methode werkt voor iedere n×n-vierkant waarbij n oneven is. Wanneer je gebruik maakt van opeenvolgende getallen vanaf 1 om een magisch vierkant te vullen dan is de magische som: Oftewel: Je telt alle getallen van 1 t/m n op en deelt deze som dan door de wortel van n. Voor een 3×3-vierkant krijg je dan: 45/3=9 en voor het 4×4-vierkant: 136/4=34. Een magisch vierkant is verder roteerbaar (90°, 180° ,270°) en horizontaal, verticaal en diagonaal spiegelbaar: Op het internet zijn heel veel sites over magische vierkanten te vinden. Zo zijn er ook generieke methodes voor een n×n vierkant waarbij n een viervoud is en generieke methodes voor een n×n vierkant met n even maar niet deelbaar door 4. En nu komt alles bij elkaar! Het spelen van het spelletje 15-en is in feite niets anders dan het spelen van Boter-Kaas-en-Eieren met het magische vierkant. Er bestaat geen winnende strategie voor BKE en dus ook niet voor 15-en. Er bestaat echter wel een strategie waarbij je nooit hoeft te verliezen, maar die laat ik graag aan de lezer dezes over… Als je tegenstander niet zo sterk speelt dan zou je het volgende eens bij BKE kunnen proberen: Als je als eerste aan de beurt bent zet dan je X in de linker bovenhoek. Je tegenspeler hoeft nog niet defensief te spelen en kan zijn O dus overal neerzetten (behalve linksboven). Als je tegenspeler de O niet in het midden zet probeer dan jouw X in een ander hoekpunt te plaatsen, zo ver mogelijk weg van de O. Deze strategie zie je op de eerste afbeelding van dit artikel. Ter herinnering: Zo’n zelfde strategie kun je nu ook bij 15-en toepassen: Analoog aan de BKE-strategie: Kies 8, tegenspeler kiest (bv.) 2. Kies 4, tegenspeler kiest 3. Kies 6, tegenspeler kiest 1. Kies 5 en je kunt nu 15 maken met 4, 5 en 6. Dus je speelt 15-en als BKE met het magische vierkant.Inleiding
Maar schijn bedriegt…15-en
Het hoeven niet per se de laatste 3 gekozen kaartjes te zijn.
S2G5,
S1G3,
S2G4,
S1G8
Doe dat maar eens een aantal keer en kijk of je van de computer kan winnen…# 15-en
import random
from itertools import combinations
stock=[]
human=[]
computer=[]
move=0
player='computer'
stop=False
defensive=True
def question(question, default):
a=input(question+' ['+default+']: ')
if a=='' or a[0].upper()==default.upper():
return True
else:
return False
def resetup():
global stock, human, computer, move, player
for i in range(1, 10):
stock.append(i)
human=[]
computer=[]
move=0
if player=='computer':
player='human'
else:
player='computer'
def setup():
global player,defensive
print('15-en')
print()
q='Do you want the computer play defensive(d) or at random(r)?'
if question(q, 'D'):
defensive=True
else:
defensive=False
if question('Do you want to start?', 'Yes'):
player='computer'
else:
player='human'
print()
resetup()
def scoreboard():
global stock, human, computer
human=sorted(human)
computer=sorted(computer)
stock=sorted(stock)
print('-----Scoreboard-------------------------')
print('Stock:', end=' ')
print(*stock, end=' ')
print('You:', end=' ')
print(*human, end=' ')
print('Computer:', end=' ')
print(*computer)
print('----------------------------------------')
def check15():
s=0
c=[]
if player=='human':
comb=combinations(human,3)
uitleg code
Voor de permutatie doet de volgorde er wel toe.
Welke combinaties (dat zijn er dus 4) van 3 elementen kan ik dan maken?
Welnu: {1, 2, 3}, {1, 2, 4}, {1, 3, 4} en {2, 3, 4}.
Boter-Kaas-en-Eieren
Doe dat maar eens een aantal keer en kijk of je van de computer kan winnen…# Tic-Tac-Toe: human vs computer
# Computer can play defensive
import random
board=[['.','.','.'],['.','.','.'],['.','.','.']]
player='X'
computer='O'
turn='human'
move=0
stop=False
#nt is used in printboard for normal-text(nt=True) or extended asccii-text(nt=False)
nt=False
defensive=True
def question(question, default):
a=input(question+' ['+default+']: ')
if a=='' or a[0].upper()==default.upper():
return True
else:
return False
def printboard(normaltext=False):
if normaltext:
print('-------')
else:
print('╔═╦═╦═╗')
for x in range(3):
if normaltext:
print(f'|{board[x][0] if board[x][0] != "." else 3*x+1}|'
f'{board[x][1] if board[x][1] != "." else 3*x+2}|'
f'{board[x][2] if board[x][2] != "." else 3*x+3}|\n-------')
else:
print(f'║{board[x][0] if board[x][0] != "." else 3*x+1}║'
f'{board[x][1] if board[x][1] != "." else 3*x+2}║'
f'{board[x][2] if board[x][2] != "." else 3*x+3}║')
if x<2:
print('╠═╬═╬═╣')
if normaltext:
print()
else:
print('╚═╩═╩═╝')
def setup():
global player, computer, turn, nt, defensive
q='Do you want plain-text(p) or Ascii-text(a) for the grid?'
if question(q, 'A'):
nt=False
else:
nt=True
q='Do you watn the computer play defensive(d) or at random(r)?'
if question(q, 'D'):
defensive=True
else:
defensive=False
q='Do you want to play with "X"?'
if question(q,'Yes'):
player='X'
computer='O'
turn='human'
else:
player='O'
computer='X'
turn='computer'
def playerturn():
global move, stop
wrong=True
while wrong:
printboard(normaltext=nt)
try:
v=int(input('Wich field (number) do you want to use?'))
except:
print('false input: Give integer number')
wrong=True
continue
if v==0:
stop=True
exit(0)
else:
f=(v-1)//3
g=(v)%3-1
if g==-1:
g=2
wrong=(board[f][g] != '.')
if wrong:
print(f'false input: Board({f+1}, {g+1}) (number {v}) is not free')
if not stop:
board[f][g]=player
move += 1
def givesum(cs):
s=0
#1st row horizontal
if cs==1:
for y in range(3):
if board[0][y]==player:
s+=2**y
#2nd row horizontal
if cs==2:
for y in range(3):
if board[1][y]==player:
s+=2**(y+3)
#3rd row horizontal
if cs==3:
for y in range(3):
if board[2][y]==player:
s+=2**(y+6)
#1st column vertical
if cs==4:
for x in range(3):
if board[x][0]==player:
s+=2**(x*3)
#2nd column vertical
if cs==5:
for x in range(3):
if board[x][1]==player:
s+=2**(x*3+1)
#3rd column vertical
if cs==6:
for x in range(3):
if board[x][2]==player:
s+=2**(x*3+2)
#Diagonal from upper left to lower right
if cs==7:
for x in range(3):
if board[x][x]==player:
s+=2**(4*x)
#Diagonal from upper right to lower left
if cs==8:
for x in range(3):
if board[2-x][x]==player:
s+=4**(x+1)
return s
def computerturn():
global move
#Defense
f=-1
if defensive:
uitleg code
Het magisch vierkant
Er zitten nog meer 2×2 vierkantjes in waarvan de som ook 34 bedraagt!
Alles bij elkaar
Herhaal dat nogmaals zodat je 3 hoekpunten bezet krijgt. Nu moet je tegenspeler wel defensief spelen, want je kunt nu wellicht een horizontale rij of een verticale kolom vullen. Maar je kunt tegelijkertijd ook één van de diagonalen vullen, zodat je bij de volgende beurt altijd zult winnen!
15-en, BKE en het magisch vierkant
Met de functie combinations uit itertools worden de verschillende combinaties van de list human met een lengte van 3 bepaald.
Het resultaat is een list.
for i in comb:
for j in range(3):
s+=i[j]
c.append(i[j])
if s==15:
break
else:
s=0
c=[]
else:
comb=combinations(computer,3)
for i in comb:
for j in range(3):
s+=i[j]
c.append(i[j])
if s==15:
break
else:
s=0
c=[]
return (s==15), sorted(c)
def humanpick():
global player, move, human
wrong=True
if move<9:
scoreboard()
while wrong:
print('\nYour turn')
print('You can choose the following number(s): ', end=' ')
print(' '.join(str(x) for x in stock))
try:
g=int(input('Choose your number: '))
except:
print('You gave a false number: Try again...')
wrong=True
continue
if g==0:
exit(0)
if g in stock:
stock.remove(g)
human.append(g)
wrong=False
else:
print('You choose a wrong number: Try again...')
wrong=True
print()
move+=1
if move>4:
w,c = check15()
if w:
print('You have won!!!')
print('Winning combination: ', end=' ')
print(*c)
return 1
else:
player='computer'
return 0
else:
player='computer'
return 0
def computerpick():
global player, move
if move<9:
scoreboard()
print('\nMy turn:')
print('I can choose one of the following numbers: ', end=' ')
print(' '.join(str(x) for x in stock))
wrong=True
#defensive
if defensive:
if move>=3:
temp=human.copy()
s=0
for i in range(1,10):
if not (i in temp) and (i in stock):
temp.append(i)
comb=combinations(temp,3)
for x in comb:
for y in range(3):
s+=x[y]
if s==15:
temp.remove(i)
wrong=False
g=i
break
else:
s=0
temp.remove(i)
while wrong:
g=random.randrange(1,10)
wrong=not(g in stock)
print(f'I choose {g}')
print()
stock.remove(g)
computer.append(g)
move+=1
if move>4:
w,c = check15()
if w:
print('I have won!!!')
print('Winning combination: ', end=' ')
print(' '.join(str(x) for x in c))
return 1
else:
player='human'
return 0
else:
player='human'
return 0
def play():
global stop
while not stop:
if move>=9:
print('It is a draw.')
stop=not(question('Play again? ', 'Y'))
if not stop:
resetup()
else:
exit(0)
elif player=='human':
if humanpick():
stop=not(question('Play again? ', 'Y'))
if not stop:
resetup()
else:
exit(0)
elif player=='computer':
if computerpick():
stop=not(question('Play again? ', 'Y'))
if not stop:
resetup()
else:
exit(0)
setup()
play()C(n,k)=nCr=\frac{n!}{k!(n-k)!}
P(n,k)=nPr=\frac{n!}{(n-k)!}
C(4,3)=\frac{4!}{3!(4-3)!}=\frac{4!}{3!.1!}=\frac{24}{6}=4
P(4,3)=\frac{4!}{(4-3)!}=\frac{4!}{1!}=\frac{24}{1}=24
Om niet eindeloos veel geneste if-elif-combinaties te krijgen is hier wat wiskunde toegepast.
Ieder veld van het vierkant heeft een uniek binair nummer gekregen.
Hiermee zal de som van iedere combinatie van cellen een unieke waarde opleveren.
De binaire getallen zijn uiteraard omgezet in decimale getallen.
for t in range(9):
s=givesum(t)
if s==3 or s==5 or s==6:
p=7-s
f=0
g=p//2
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==24 or s==40 or s==48:
p=56-s
f=1
g=p//16
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==192 or s==320 or s==384:
p=448-s
f=2
g=p//128
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==9 or s==65 or s==72:
p=73-s
g=0
f=round((p**(1/3))*0.5)
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==18 or s==130 or s==144:
p=146-s
g=1
f=round(p**0.25)-1
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==36 or s==260 or s==288:
p=292-s
g=2
f=round((p**0.25)//2)
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==17 or s==257 or s==272:
p=273-s
f=(p**0.25)//2
g=f
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if s==20 or s==68 or s==80:
p=84-s
g=(p**0.5)//4
f=-g+2
if board[int(f)][int(g)]=='.':
break
else:
f=-1
if f==-1:
wrong=True
while wrong:
v=random.randint(1,9)
f=(v-1)//3
g=(v)%3-1
if g==-1:
g=2
wrong=(board[f][g] != '.')
board[int(f)][int(g)]=computer
move += 1
def score():
global turn
pw=False
cw=False
for x in range(3):
if board[x][0] == player and board[x][1] == player and board[x][2] == player:
pw=True
if not pw:
for y in range(3):
if board[0][y] == player and board[1][y] == player and board[2][y] == player:
pw=True
if not pw:
if (board[0][0] == player and board[1][1] == player and board[2][2] == player) or \
(board[0][2] == player and board[1][1] == player and board[2][0] == player):
pw=True
if pw:
printboard(normaltext=nt)
print('You have won!!!')
return 1
for x in range(3):
if board[x][0] == computer and board[x][1] == computer and board[x][2] == computer:
cw=True
if not pw:
for y in range(3):
if board[0][y] == computer and board[1][y] == computer and board[2][y] == computer:
cw=True
if not pw:
if (board[0][0] == computer and board[1][1] == computer and board[2][2] == computer) or \
(board[0][2] == computer and board[1][1] == computer and board[2][0] == computer):
cw=True
if cw:
printboard(normaltext=nt)
print('I have won!!!')
return 1
if move == 9:
printboard(normaltext=nt)
print("It's a draw!")
return 1
if turn == 'human':
turn='computer'
else:
turn='human'
return 0
def play():
global turn, stop, player, computer, board, move
while not stop:
if turn=='human':
playerturn()
p=score()
else:
computerturn()
p=score()
if p == 1:
stop=not question('Play Again?', 'Yes')
move=0
if not stop:
board=[['.','.','.'],['.','.','.'],['.','.','.']]
if question('Do you want to play with "X"?', 'Yes'):
player='X'
computer='O'
turn='human'
else:
player='O'
computer='X'
turn='computer'
setup()
print(f'{"You" if turn=="human" else "Computer"} play{"s" if turn=="Computer" else ""} with X.')
play()
#defensive play:
#used grid
# 84
# 1 2 4 7
# 8 16 32 56
# 64 128 256 488
#
# 73 146 292 273
#
# numbers in grid are decimal representitives of binairy numbers (000000001 to 100000000),
# wich ensures unique sums of all different combinations of cells
#\frac{\sum\limits_{k=1}^{n}k}{\sqrt{n}}