I am trying to develop a swiss tournament pairing algorithm and I am essentially using a backtracking algorithm that gives a value for each terminal position based on how well it has matched the players. It seems to mostly be working but it will for some reason allow an empty pairing list with a penalty value of 0 to be returned. I have been looking at this code for hours. Any insight would be appreciated!
Python:
#Calculates the penalty value of a pairing
def calculatePairingPenalty(self, pairing: Pairing) -> int:
if pairing.white in pairing.black.playedAgainst:
return 999999999
return math.pow(pairing.white.points - pairing.black.points, 2)
#Calculates the total penalty value of a pairing list
def calculateTotalPenalty(self, pairings: list[Pairing]):
if len(pairings) != len(self.players)/2:
return 99999999
totalPenalty = 0
for pairing in pairings:
totalPenalty += self.calculatePairingPenalty(pairing)
return totalPenalty
# minMax/backtracking type of algorhitm
def generateNewRound(self, pairings: list[Pairing]):
if len(pairings) == len(self.players)/2: # if everyone has been paired return pairings
#for i in pairings:
# print(i.white.name + " : " + i.black.name)
#print(self.calculateTotalPenalty(pairings))
return pairings
bestPairings: list[Pairing] = []
penaltyScore = 999999
#Tries all possible permutations, needs to be optimized
for player in self.players:
if player.isPaired: continue
for opponent in self.players:
if opponent.isPaired or player.name == opponent.name or opponent in player.playedAgainst: continue
pairings.append(Pairing(player, opponent))
player.isPaired = True
opponent.isPaired = True
newPairings = self.generateNewRound(pairings)
newPenaltyScore = self.calculateTotalPenalty(newPairings)
if newPenaltyScore < penaltyScore:
penaltyScore = newPenaltyScore
bestPairings = newPairings
player.isPaired = False
opponent.isPaired = False
pairings.pop()
return bestPairings