Блог

Я написал рекурсивный алгоритм, чтобы решить, какой ход должен делать компьютер при игре в крестики-нолики против человек. Мое первоначальное решение состояло из набора возможных ходов из заданного состояния доски и оценивало каждый ход на основе того, сколько выигрышей и проигрышей могло произойти в результате этого начального хода — плюс одно очко за каждый выигрыш, минус одно очко за каждый проигрыш.

Это работает во многих ситуациях, но я заметил, что были случаи, когда компьютер мог выиграть сразу всего одним ходом, но сделал другой ход, и я понял, что это связано с тем, что этот беспроигрышный ход мог привести к 3 победам и без потерь (несколько ничьих, которые в моей программе считаются 0 очками), поэтому он получил 3 очка, в то время как выигрышный ход получил только 1 очко.

Чтобы решить эту проблему, я взвесил количество очков, которое конкретный результат внес в общую оценку начального хода, обратно пропорционально рекурсивной глубине: points = outcome / (depth 1) . Таким образом , выигрыш в 1 ход будет стоить (1 pt for win) / (0 for depth 1) = 1/1 = 1 того, в то время как выигрыш в 2 хода будет стоить 1/2 того .

К сожалению, в игре в крестики-нолики есть случай, когда выигрыш возможен за 1 ход, но другой не выигрышный ход, в свою очередь, дает 3 возможных выигрышных хода. Так что даже с моим весом 3 победы =gt; 1,5 очка против 1 победы =gt;gt; 1 очко.

В конце концов, я решил эту проблему, умножив баллы на рекурсивной глубине=0 на бесконечность, так что 1 ход с бесконечными очками стоит бесконечности. Хотя это заставляет программу работать должным образом, это похоже на «мошенничество» алгоритмически, и, насколько я знаю, подобный подход не сработал бы с более сложным алгоритмом для задачи более сложной, чем крестики-нолики. Существует ли «правильный» способ подхода к взвешиванию алгоритмических «оценок», когда вы хотите, чтобы алгоритм предпочитал определенные результаты, но также и более ранние результаты?