Как создать функцию оценки результата для настольной игры (wizwoz)
Игра называется wizwoz:
Два игрока, красный (обозначенный как r) и золотой (обозначенный как g), первоначально выбирают два значения n и k. Доска n × n создается с k "r" и k "g", расположенными случайным образом на доске. Начиная с игрока r, каждый игрок помещает свою букву ("r" для игрока r, "g" для плательщика g) в один из пустых квадратов на доске. После того, как доска заполнена, оценка каждого игрока равна самой большой соединенной области на доске, заполненной цветом этого игрока (где подключенная область - та, где для любых двух квадратов в области существует путь, состоящий только из N/S/E/W движется). Игрок с наибольшим количеством очков выигрывает, и ему присуждается разница между его / ее счетом и счетом другого игрока. Ниже приведены два примера готовых игр с выделением наибольших областей для каждого игрока. Обратите внимание, что во втором примере два раздела с 2 r каждый не связаны.
Я пишу алгоритм отсечения альфа-бета и придерживаюсь функции оценки.
Любая помощь? Псевдокод предпочтительнее.
1 ответ
Начните с очень простой оценочной функции. Например, просто используйте текущий размер самого большого компонента. После того, как вы приступите к работе, вы можете заняться настройкой эвристики оценки.
Вот пример псевдокода (не тестировался)
components = {k:set([k]) for k in board}
def contract(k1, k2):
if color(k1) != color(k2):
return
new = components[k1]
if k2 not in new:
new.union_update(components[k2])
for x in components[k2]:
components[x] = new
for x,y:
contract(board[x,y], board[x,y+1])
contract(board[x,y], board[x+1,y])
return max(map(len, components))