Game Theory

В тази секция ще разгледаме основите на "теория на игрите" в състезателното програмиране. Ще научим какво е "оптимална игра" и как можем да намерим победителя в такава. Ще покажем минимакс стратегии (в които искаме да максимизираме нашия резултат и да минимизираме този на противника). Ще застъпим и основната теория зад много от състезателните задачи: числата на Грунди, които също може да срещнете като SG числа или пък NIMbers (кръстени на играта NIM). Реално теорията отзад е доста сложна, но пък прилагането й (което всъщност ви интересува в повечето задачи) е относително просто. Макар и плашеща на пръв поглед, това е една що-годе лесна секция.

За минаването през секцията ще ви помогне темата Теория на игрите.

Задачите в секцията ползват или minimax, или SG, или комбинация на предните две с някакъв друг алгоритъм.