Игри и алгоритъм минимакс

Миналия час търсехте път в граф, в който всички ходове са ваши. В играта е различно: след вашия ход идва ход на противника, който иска обратното на вас. Планът „ще направя А, после Б, после В“ не струва, ако противникът след А играе нещо, което сте пропуснали.

Компютърът решава това с търсене, но с една добавка: на всяко второ ниво в графа не избира той, а противникът. Така през 1997 г. Deep Blue побеждава световния шампион Гари Каспаров — не с разбиране на шаха, а с проверка на огромен брой продължения и една добра оценка на позицията.

В морски шах първият има 9 хода, вторият — 8, после 7… най-много 9! = 362 880 последователности, а различните позиции са няколко хиляди. Компютърът обхожда всичко за части от секундата и играе безгрешно. В шаха от една позиция има средно около 30 хода и дървото става необозримо още на няколко нива — за това накрая.

За да сравняваме ходове, всяка позиция трябва да получи число. Нека компютърът играе с X. Крайните позиции са лесни:

В морски шах това стига — дървото се обхожда до края и всяка позиция получава оценка от децата си. В шаха краят е недостижим и позицията се оценява приблизително — с евристика като в урок 8. Най-простата брои материала: пешка 1, кон и офицер 3, топ 5, дама 9; оценката е „моят материал минус неговия“.

Компютърът иска най-високата оценка — той е MAX. Противникът иска най-ниската — той е MIN. Ходовете се редуват, значи нивата в дървото се редуват: MAX, MIN, MAX, MIN…

1. Оценете листата — крайните позиции или позициите на границата на дълбочината.
2. Възел на ниво MIN получава най-малката оценка от децата си: противникът ще избере най-лошото за нас.
3. Възел на ниво MAX получава най-голямата: ние избираме най-доброто за нас.
4. Повтаряйте отдолу нагоре до корена. Най-добрият ход е детето на корена с най-висока оценка.

Един ход напред е дълбочина 1; вашият ход и отговорът на противника — дълбочина 2. При средно 30 хода на позиция:

Всяко ниво умножава работата по 30. Затова се търси до определена дълбочина и там позициите се оценяват с евристиката. Колкото по-дълбоко, толкова по-силна игра — но и толкова по-бавна.

• Ефект на хоризонта — на границата оценката не вижда какво следва: „взех кон“ изглежда добре на дълбочина 2, ако загубата на дамата е на дълбочина 3.
• Отрязване — щом за даден ход противникът вече има отговор, по-лош за нас от друг наш ход, останалите му отговори не се гледат. Това е алфа-бета отрязването и удвоява достижимата дълбочина без да променя резултата.
• Deep Blue проверява около 200 милиона позиции в секунда — и въпреки това не стига до края на партията.

Дъската е масив от 9 знака: 'X', 'O' или '.'. Методът връща оценката на позицията при най-добра игра на двамата. Той извиква сам себе си за всяко дете — това е рекурсия, която ще учите в Модул 2.

// Оценка на позицията при най-добра игра. Компютърът е X.
static int Minimax(char[] d, bool redNaX)
{
    char p = Pobeditel(d);            // 'X', 'O' или '.' (няма)
    if (p == 'X') return 1;
    if (p == 'O') return -1;
    if (Array.IndexOf(d, '.') < 0) return 0;   // пълна дъска — равен

    int nayDobra = redNaX ? -2 : 2;   // по-лошо от всичко възможно
    for (int i = 0; i < 9; i++)
    {
        if (d[i] != '.') continue;
        d[i] = redNaX ? 'X' : 'O';     // правим хода
        int ocenka = Minimax(d, !redNaX);   // какво следва след него
        d[i] = '.';                    // връщаме го обратно
        if (redNaX && ocenka > nayDobra) nayDobra = ocenka;    // MAX
        if (!redNaX && ocenka < nayDobra) nayDobra = ocenka;   // MIN
    }
    return nayDobra;
}

• Първите четири реда са листата: победа, загуба, равен.
• Цикълът пробва всеки свободен ход, оценява го и го връща — така една дъска стига за цялото дърво.
• Двата if накрая са цялата разлика между MAX и MIN.
• За да намерите най-добрия ход, извикайте Minimax за всяко дете на корена и вземете най-високата оценка.

• Дърво на играта: корен — текущата позиция, нива — редуващи се ходове на двамата.
• Оценка: +1 / 0 / −1 в края; при отрязана дълбочина — евристика (например материалът).
• MAX взима най-голямата оценка от децата, MIN — най-малката. Отдолу нагоре до корена.
• Минимакс избира хода с най-добрия гарантиран резултат при най-добра игра на противника.
• Дълбочината е ограничена, защото работата расте степенно; отрязването помага, хоризонтът остава.