Кіріспе

Комбинаторлық ойын теориясындағы ұғым

Комбинаторлық ойын теориясы ойынның күрделілігін бірнеше тәсілмен өлшейді:

Кейбір жағдай кеңістігінің күрделілігі (бастапқы позициядан бастап қолданылатын ойын позицияларының саны),
Ойын ағашының көлемі (мүмкін болатын ойындардың жалпы саны),
Шешім қабылдаудың күрделілігі (бастапқы позиция үшін ең кішкентай шешім ағашындағы жапырақ түйіндерінің саны),
Ойын ағашының күрделілігі (бастапқы позиция үшін ең кішкентай толық енді шешім ағашындағы жапырақ түйіндерінің саны),
Есептеу күрделілігі (ойынның кез келген деңгейде үлкейгендегі асимптотикалық қиындығы). Бұл өлшемдер ойын позицияларын, мүмкін нәтижелерді және түрлі ойын сценарийлері үшін қажетті есептеулерді түсінуді қамтиды.

Мемлекеттер кеңістігінің күрделілігі

Ойынның күй кеңістігінің күрделілігі – ойынның бастапқы позициясынан қол жетімді заңды ойын позицияларының саны. Егер позициялардың айналуы мен көрінісі бірдей саналса, онда бар болғаны 765 әртүрлі позиция болады. Ойын ағашын шектеу үшін 9 мүмкін бастапқы қимыл, 8 мүмкін жауап және т.б. бар, сондықтан барлығында 9! немесе 362 880 ойынға дейін болуы мүмкін. Дегенмен, ойындарды шешу үшін 9 қимылдан да аз қажет болуы мүмкін, ал нақты санау 255 168 мүмкін ойынды көрсетеді. Позициялардың айналуы мен көрінісі бірдей саналса, онда бар болғаны 26 830 мүмкін ойын болады. Tic Tac Toe-ның есептеу күрделілігі оның жалпылануына байланысты. Табиғи жалпылау – m,n,k ойындары: m x n тақтада ойналады, жеңімпаз k белгіні қатарға бірінші тізген ойыншы болады. Бұл ойынды бүкіл ойын ағашын іздеу арқылы DSPACE(mn) арқылы шешуге болады екені бірден көрінеді. Бұл оны маңызды күрделілік классы PSPACE-ке жатқызады. Тағы бірнеше жұмыс жасаса, оның PSPACE-толық екенін көрсетуге болады.