Ігрові задачі

Ігрові задачі є типовим класом задач, які традиційно відносять до інтелектуальних. Оскільки вибір чергового ходу в іграх є не що інше, як прийняття рішення, методи програмування ігрових задач найтіснішим чином пов'язані з методами планування цілеспрямованих дій і прийняття рішень.

Характерною особливістю ігрових задач є наявність суперника, який активно перешкоджає здійсненню цілей, які ставить перед собою кожний гравець.

Теорія ігор є важливою складовою частиною дослідження операцій. Її перше систематизоване викладення було зроблено Нейманом і Моргенштерном у 1944, хоча перші результати припадають на 20-і роки.

Для побудови систем штучного інтелекту найбільший інтерес становлять методи знаходження планів гри і оптимальних стратегій для таких ігор, як шахи, шашки, «хрестики-нулики» тощо З точки зору теорії ці ігри є ідентичними між собою. Вони належать до класу позиційних ігор двох осіб. Кожний гравець може по черзі зробити будь-який хід з тих, які дозволяються правилами гри. Ці ігри є детермінованими у тому розумінні, що перебіг гри та вибір ходу не залежать від випадкових чинників. Крім того, це є ігри з повною інформацією, тобто кожному гравцеві доступна вся інформація про будь-яку позицію, яка утворюється в процесі гри. Нарешті, вказані ігри належать до класу антагоністичних ігор, або ігор з нульовою сумою. Це означає, що сума виграшів обох гравців дорівнює нулю, тобто виграш одного гравця дорівнює програшу іншого. З цього випливає, що замість двох функцій виграшу можна розглядати одну.

Можна назвати відомі позиційні ігри, які належать до інших класів. Так, нарди є грою з повною інформацією, але не є детермінованою у тому розумінні, що гравець не може зробити довільний хід; його вибір обмежений випадковими чинниками. Преферанс не є грою з повною інформацією і не є грою детермінованою у тому розумінні, що початкова позиція залежить від випадку. Але після того, як початкова позиція зафіксована, гравець може зробити будь-який хід, який дозволений правилами.