Игри (проект за курс)
	=====================

1. Игри (уводна лекция)

Дефиниция (неформална): конфликт, който се развива по предварително уговорени правила.

Примери: футбол, шах, табла, бридж, бикове и крави, морски шах, преследване на елен от 3 вълка (преследване)

Правила: позиция, играчи, ходове, правила за край на играта, печалба на играчите в края

Типове игри: 

Играта може да се поддава на формално описание на правилата и самото й протичане - можем да наречем такава игра математическа (шах, табла, бридж). Ако не се поддава на пълна формализация, можем да наречем играта спортна (футбол).

Според наличието на подробна информация за ходовете мат. игри се делят на игри с пълна информация (играча вижда какъв ход прави противника) и игри с непълна информация (двамата играчи правят ход едновременно).

Според наличието на случаен елемент в хода мат. игри ги делим на логически (няма случаен елемент - шах, дама) и игри със случаен ход (табла, бридж). Когато всички ходове са случайни играта е хазартна.

Според броя на възможните позиции и ходове играта е крайна (шах) или безкрайна (преследване на жертва от глутница).

Според печалбата на играчите - игри с нулева сума (ако единия печели, другия губи същото количество), игри с ненулева сума (може и двамата играчи да спечелят).

2. Компютърна реализация на мат. игра (основни техники).

Граф породен от позициите (върхове) и ходовете (ребра). Точна оценяща функция на играта. 
Минимаксна процедура за изчисляване на оценящата функция.
Пример за лесна оценяща функция - играта ним (книжката на Чуканов !)

---------------------------

3. Дървета, дърво на играта породено от позиция и ходовете в дълбочина.
   Приближена оценяща функция. 

4. Изследване на дървото на ходовете в дълбочина, рекурсия, стек.

5. Подобрения на минимаксния алгоритъм:
   алфа-бета отсичане
   кеширане на оценените позции

---------------------------

6. Симетрични позиции в играта "дама".
   Група на симетриите, геометрична и алгебрична (пермутации) интерпретация.
   Пораждане на групата на симетриите, изчисляване на обратните елементи.

7. Специфични похвати за подобряване на играта на програмата за "дама".
   Използване на симетриите за намаляване на броя оценявани позиции при дебюта.
   Ендшпили - изчисляване на ендшпили с помощта на симетриите.
   Мителшпили, форсирани позиции, оценка на форсирани позиции.

---------------------------

8. Игри с непълна информация. Смесени стратегии.

9. Приложения на игрите с непълна информация (примери от еволюционната теория).

10. Игра "преследване" - геометрична интерпретация

---------------------------

11. Игри със случаен ход. Бикове и крави, бридж, морски шах.

12. Приложения на игрите със сл. ход - съставяне на карта на ДНК.


---------------------------



===========================

		Анотация

Игрите са присъщи не само на хората, а и на всички интелигентни животни които полагат грижи за малките си.

В човешките култури пособията за игри се откриват в най-древните исторически пластове.

Игрите са важна част от компютърните приложения и освен за развлечение се ползват като инструмент за моделиране и решаване на важни задачи в различни науки и сфери на дейност, най-вече в икономиката, биологията и военното планиране.

Този курс е посветен на игрите и тяхната компютърна реализация.

Ще опишем различните типове игри.