Как создать функцию оценки результата для настольной игры (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))
Другие вопросы по тегам