Как использовать Манхэттен Расстояние, чтобы решить эту игру?

Question

Каждый игрок по очереди убирает 1 или 2 банана из корзины из 50 бананов. Игрок, который опустошает корзину, побеждает.

Какие веса следует использовать для расстояний и каким должен быть размер матрицы? Должна ли матрица меняться каждый раз, когда кто-то делает ход? Должны ли ходы игрока 1 быть горизонтальными, а ходы игрока 2 - вертикальными?

Спасибо за прочитанное

Answer 1

Я не уверен, почему вы специально хотите использовать динамическое программирование и / или манхэттенское расстояние для этой головоломки. Это игра, для которой вы можете найти фиксированное решение.

Если вы идете первыми и у вас есть 3 банана, независимо от того, во что вы играете, я выигрываю. Вы выбираете один, я выбираю два, и наоборот. Если есть шесть бананов, та же логика позволяет мне свести игру к 3 бананам. Фактически, для любых 3n бананов я могу уменьшить игру до 3(n-1) бананов. Если количество бананов не кратно трем, вы можете сделать его кратным трем (удалив один или два банана) и обеспечить победу.

Для k бананов вы всегда удаляете k % 3, Если k % 3 == 0Вы проиграли, если ваш оппонент не совершил ошибку, поэтому играйте все, что захотите. Вот и все.

Answer 2

Я согласен с @pdpi, но если вы настаиваете на решении этой проблемы с помощью динамического программирования, то вы должны сделать что-то вроде этого:

f(left_in_the_basket, mine)
    if left_in_the_basket is 2 && turn is mine:
        return 1
    if left_in_the_basket is 1 && turn is mine:
        return 1
    if left_in_the_basket is 2 && turn is not mine:
        return -1
    if left_in_the_basket is 1 && turn is not mine:
        return -1
    return max (f(left_in_the_basket - 1, not mine), f(left_in_the_basket - 2, not mine))