ทฤษฎีเกมเชิงการจัดเรียง (Combinatorial game theory)วัดความซับซ้อนของเกมได้หลายวิธี:

1. ความซับซ้อนของปริภูมิสถานะ (จำนวนตำแหน่งเกมที่ถูกต้องตามกฎจากตำแหน่งเริ่มต้น)
2. ขนาดของโครงสร้างเกม (จำนวนเกมที่เป็นไปได้ทั้งหมด)
3. ความซับซ้อนของการตัดสินใจ (จำนวนโหนดใบในต้นไม้ตัดสินใจที่เล็กที่สุดสำหรับตำแหน่งเริ่มต้น)
4. ความซับซ้อนของโครงสร้างต้นไม้เกม (จำนวนโหนดใบในต้นไม้ตัดสินใจที่มีความกว้างเต็มที่ที่เล็กที่สุดสำหรับตำแหน่งเริ่มต้น)
5. ความซับซ้อนในการคำนวณ (ความยากเชิงอะซิมโทติกของเกมเมื่อค่าของเกมเพิ่มขึ้นอย่างไม่จำกัด)

มาตรการเหล่านี้เกี่ยวข้องกับการทำความเข้าใจสถานการณ์ในเกม ผลลัพธ์ที่เป็นไปได้ และความซับซ้อนในการคำนวณของสถานการณ์เกมต่างๆ

ความซับซ้อนของปริภูมิสถานะของเกมคือจำนวนตำแหน่งเกมที่ถูกต้องตามกฎหมายที่สามารถเข้าถึงได้จากตำแหน่งเริ่มต้นของเกม^{[ 1 ]}

เมื่อการคำนวณค่านี้ยากเกินไป มักจะสามารถคำนวณ ค่าขอบเขตบนได้โดยการนับรวมตำแหน่งที่ไม่ถูกต้องบางส่วน (ตำแหน่งที่ไม่สามารถเกิดขึ้นได้ในระหว่างเกม) ด้วย

ขนาดของต้นไม้เกมคือจำนวนเกมทั้งหมดที่เป็นไปได้ที่สามารถเล่นได้ ซึ่งก็คือจำนวนโหนดใบในต้นไม้เกมที่เริ่มต้นจากตำแหน่งเริ่มต้นของเกมนั้น

โดยทั่วไปแล้ว แผนผังเกมจะมีขนาดใหญ่กว่าปริภูมิสถานะมาก เนื่องจากตำแหน่งเดียวกันสามารถเกิดขึ้นได้ในหลายเกมโดยการเดินหมากในลำดับที่แตกต่างกัน (ตัวอย่างเช่น ใน เกม โอเอ็กซ์ที่มีตัว X สองตัวและตัว O หนึ่งตัวบนกระดาน ตำแหน่งนี้สามารถเกิดขึ้นได้สองวิธีที่แตกต่างกัน ขึ้นอยู่กับว่าวางตัว X ตัวแรกไว้ที่ใด) บางครั้งสามารถคำนวณขอบเขตบนของขนาดแผนผังเกมได้โดยการทำให้เกมง่ายขึ้นในลักษณะที่จะเพิ่มขนาดของแผนผังเกมเท่านั้น (ตัวอย่างเช่น โดยการอนุญาตให้มีการเดินหมากที่ผิดกฎ) จนกว่าจะสามารถจัดการได้ง่ายขึ้น

สำหรับเกมที่จำนวนการเดินหมากไม่จำกัด (เช่น โดยขนาดของกระดาน หรือโดยกฎเกี่ยวกับการซ้ำตำแหน่ง) โดยทั่วไปแล้ว แผนผังการเดินหมากจะมีขนาดเป็นอนันต์

แผนผังการตัดสินใจเป็นแผนผังย่อยของแผนผังเกม โดยแต่ละตำแหน่งจะถูกกำกับด้วยข้อความว่า "ผู้เล่น A ชนะ", "ผู้เล่น B ชนะ" หรือ "เสมอ" หากสามารถพิสูจน์ได้ว่าตำแหน่งนั้นมีค่าดังกล่าว (โดยสมมติว่าทั้งสองฝ่ายเล่นอย่างดีที่สุด) โดยการพิจารณาเฉพาะตำแหน่งอื่นๆ ในกราฟเท่านั้น ตำแหน่งสุดท้ายสามารถกำกับข้อความได้โดยตรง—เมื่อผู้เล่น A เป็นฝ่ายเดิน ตำแหน่งนั้นสามารถกำกับข้อความว่า "ผู้เล่น A ชนะ" หากตำแหน่งถัดไปใดๆ ก็ตามเป็นผลดีสำหรับ A; "ผู้เล่น B ชนะ" หากตำแหน่งถัดไปทั้งหมดเป็นผลดีสำหรับ B; หรือ "เสมอ" หากตำแหน่งถัดไปทั้งหมดเป็นผลเสมอหรือเป็นผลดีสำหรับ B (เมื่อผู้เล่น B เป็นฝ่ายเดิน ตำแหน่งที่สอดคล้องกันจะถูกทำเครื่องหมายในทำนองเดียวกัน)

วิธีการวัดความซับซ้อนของเกมสองวิธีต่อไปนี้ใช้แผนผังการตัดสินใจ:

ความซับซ้อนของการตัดสินใจในเกม คือ จำนวนโหนดใบในต้นไม้ตัดสินใจที่เล็กที่สุดซึ่งกำหนดค่าของตำแหน่งเริ่มต้น

ความซับซ้อนของต้นไม้เกมคือจำนวนโหนดใบใน ต้นไม้ตัดสินใจ แบบเต็มความกว้าง ที่เล็กที่สุด ซึ่งกำหนดค่าของตำแหน่งเริ่มต้น^{[ 1 ]}ต้นไม้แบบเต็มความกว้างประกอบด้วยโหนดทั้งหมดในแต่ละระดับความลึก นี่เป็นการประมาณจำนวนตำแหน่งที่ต้องประเมินใน การค้นหา แบบมินิแม็กซ์เพื่อกำหนดค่าของตำแหน่งเริ่มต้น

แม้แต่การประมาณความซับซ้อนของโครงสร้างเกมก็ยังทำได้ยาก แต่สำหรับบางเกมสามารถประมาณได้โดยใช้สูตร โดยที่b คือ ค่าสัมประสิทธิ์การแตกกิ่งเฉลี่ยของเกมและdคือจำนวนตาเดินในเกมโดยเฉลี่ย ${\displaystyle GTC\geq b^{d}}$

ความซับซ้อนในการคำนวณของเกมอธิบายถึง ความยาก เชิงอะซิมโทติกของเกมเมื่อขนาดเกมใหญ่ขึ้นเรื่อยๆ โดยแสดงในรูปสัญกรณ์บิ๊กโอหรือในรูปของการเป็นสมาชิกในกลุ่มความซับซ้อนแนวคิดนี้ไม่ได้ใช้กับเกมเฉพาะเจาะจง แต่ใช้กับเกมที่ได้รับการขยายให้มีขนาดใหญ่ขึ้นได้ โดยทั่วไปแล้วจะทำได้โดยการเล่นบน กระดานขนาด nคูณn (จากมุมมองของความซับซ้อนในการคำนวณ เกมบนกระดานขนาดคงที่ถือเป็นปัญหาจำกัดที่สามารถแก้ไขได้ใน O(1) ตัวอย่างเช่น โดยใช้ตารางค้นหาจากตำแหน่งต่างๆ เพื่อหาการเดินที่ดีที่สุดในแต่ละตำแหน่ง)

ความซับซ้อนเชิงอะซิมโทติกถูกกำหนดโดยอัลกอริทึมที่มีประสิทธิภาพที่สุดสำหรับการแก้ปัญหาเกม (โดยคำนึงถึงทรัพยากรการคำนวณ ใดๆ ก็ตาม ) มาตรวัดความซับซ้อนที่ใช้กันทั่วไป คือ เวลาในการคำนวณซึ่งมักจะมีขอบเขตล่างโดยลอการิทึมของความซับซ้อนของปริภูมิสถานะเชิงอะซิมโทติก เนื่องจากอัลกอริทึมการแก้ปัญหาต้องใช้งานได้กับทุกสถานะที่เป็นไปได้ของเกม และจะมีขอบเขตบนโดยความซับซ้อนของอัลกอริทึมใดๆ ที่ใช้งานได้กับกลุ่มเกมนั้นๆ ข้อสังเกตที่คล้ายกันนี้ใช้กับมาตรวัดความซับซ้อนที่ใช้กันมากเป็นอันดับสอง คือ ปริมาณพื้นที่หรือหน่วยความจำคอมพิวเตอร์ที่ใช้ในการคำนวณ ไม่ชัดเจนว่ามีขอบเขตล่างใดๆ สำหรับความซับซ้อนของพื้นที่สำหรับเกมทั่วไปหรือไม่ เพราะอัลกอริทึมไม่จำเป็นต้องจัดเก็บสถานะของเกม อย่างไรก็ตาม เกมที่น่าสนใจหลายเกมเป็นที่ทราบกันว่าเป็นเกมที่ยากในระดับ PSPACEและด้วยเหตุนี้ ความซับซ้อนของพื้นที่ของเกมเหล่านั้นจึงมีขอบเขตล่างโดยลอการิทึมของความซับซ้อนของปริภูมิสถานะเชิงอะซิมโทติกเช่นกัน (ในทางเทคนิคแล้ว ขอบเขตนี้เป็นเพียงพหุนามในปริมาณนี้ แต่โดยทั่วไปแล้วมักเป็นเชิงเส้น)

• กลยุทธ์การค้นหาแบบมินิแม็กซ์เชิงลึก จะใช้เวลาในการคำนวณเป็นสัดส่วนกับความซับซ้อนของโครงสร้างต้นไม้ของเกม (เนื่องจากต้องสำรวจต้นไม้ทั้งหมด) และใช้หน่วยความจำในปริมาณที่เป็นพหุนามในลอการิทึมของความซับซ้อนของโครงสร้างต้นไม้ (เนื่องจากอัลกอริทึมต้องจัดเก็บโหนดหนึ่งของต้นไม้ไว้ที่ระดับความลึกของการเคลื่อนที่ที่เป็นไปได้แต่ละระดับเสมอ และจำนวนโหนดที่ระดับความลึกของการเคลื่อนที่สูงสุดก็คือความซับซ้อนของโครงสร้างต้นไม้พอดี)
• การเหนี่ยวนำย้อนกลับจะใช้ทั้งหน่วยความจำและเวลาตามสัดส่วนของความซับซ้อนของปริภูมิสถานะ เนื่องจากต้องคำนวณและบันทึกการเคลื่อนไหวที่ถูกต้องสำหรับแต่ละตำแหน่งที่เป็นไปได้

สำหรับเกมโอเอ็กซ์ขอบเขตบนอย่างง่ายสำหรับขนาดของปริภูมิสถานะคือ 3⁹ ⁼ 19,683 (มีสามสถานะสำหรับแต่ละช่องทั้งเก้าช่อง) จำนวนนี้รวมถึงตำแหน่งที่ไม่ถูกต้องหลายตำแหน่ง เช่น ตำแหน่งที่มีกากบาทห้าอันและไม่มีวงกลม หรือตำแหน่งที่ผู้เล่นทั้งสองมีแถวสามอัน การนับที่ละเอียดกว่าโดยการลบตำแหน่งที่ไม่ถูกต้องเหล่านี้ออก จะได้ 5,478 ^{[ 2 ] [ 3 ]}และเมื่อพิจารณาการหมุนและการสะท้อนของตำแหน่งว่าเหมือนกัน จะมีตำแหน่งที่แตกต่างกันโดยพื้นฐานเพียง 765 ตำแหน่งเท่านั้น

เพื่อจำกัดขอบเขตของโครงสร้างเกม จะมีการเดินหมากเริ่มต้นที่เป็นไปได้ 9 แบบ การตอบโต้ที่เป็นไปได้ 8 แบบ และอื่นๆ ไปเรื่อยๆ ดังนั้นจึงมีเกมทั้งหมดอย่างมากที่สุด 9! หรือ 362,880 เกม อย่างไรก็ตาม เกมอาจใช้เวลาน้อยกว่า 9 ตาเดินในการจบ และการนับอย่างแม่นยำจะให้เกมที่เป็นไปได้ 255,168 เกม เมื่อพิจารณาการหมุนและการสะท้อนของตำแหน่งว่าเหมือนกัน จะมีเกมที่เป็นไปได้เพียง 26,830 เกมเท่านั้น

ความซับซ้อนในการคำนวณของเกมโอเอ็กซ์ขึ้นอยู่กับวิธีการวางนัยทั่วไปการวางนัยทั่วไปตามธรรมชาติคือเกมm , n , k : เล่นบน กระดานขนาด m x nโดยผู้ชนะคือผู้เล่นคนแรกที่ได้kแถว เกมนี้สามารถแก้ได้ในDSPACE ( mn ) โดยการค้นหาต้นไม้เกมทั้งหมด ซึ่งทำให้เกมนี้อยู่ในคลาสความซับซ้อนที่สำคัญPSPACE ; ด้วยการทำงานเพิ่มเติม สามารถแสดงให้เห็นว่าเป็นPSPACE-completeได้^{[ 4 ]}

เนื่องจากความซับซ้อนของเกมมีมาก ตารางนี้จึงแสดงค่าสูงสุดของลอการิทึมฐาน 10 (กล่าวคือ จำนวนหลัก) ตัวเลขทั้งหมดต่อไปนี้ควรพิจารณาด้วยความระมัดระวัง การเปลี่ยนแปลงเล็กน้อยในกฎของเกมอาจเปลี่ยนแปลงตัวเลข (ซึ่งมักเป็นการประมาณคร่าวๆ อยู่แล้ว) ไปอย่างมหาศาล ซึ่งอาจมากกว่าตัวเลขที่แสดงไว้มาก

เกม	ขนาดกระดาน (ตำแหน่ง)	ความซับซ้อนของปริภูมิสถานะ (ในรูปของลอการิทึมฐาน 10)	ความซับซ้อนของโครงสร้างเกม (ในรูปของลอการิทึมฐาน 10)	ระยะเวลาเฉลี่ยของเกม ( ชั้น )	ปัจจัยการแตกแขนง	อ้างอิง	ระดับความซับซ้อนของเกมทั่วไป ที่เหมาะสม
เกมโอเอ็กซ์	9	3	5	9	4		PSPACE-complete [ 5 ]
ซิม	15	3	8	14	3.7		PSPACE-complete [ 6 ]
เพนโตมิโน	64	12	18	10	75	[ 7 ] [ 8 ]	?, แต่ในPSPACE
คอนเน็กต์โฟร์	42	12 (4,531,985,219,092)	21	36	4	[ 1 ] [ 9 ] [ 10 ]	?, แต่ในPSPACE
กาละห์[ 11 ]	14	13	18		50	[ 7 ]	การสรุปโดยทั่วไปยังไม่ชัดเจน
ครอบงำ (8 × 8)	64	15	27	30	8	[ 7 ]	?, แต่ในPSPACE ; ในPสำหรับมิติบางมิติ[ 12 ]
คองกัก	14	15	33			[ 7 ]
หมากรุกอังกฤษ (8x8) (เช็คเกอร์)	32	20 หรือ 18	40	70	2.8	[ 1 ] [ 13 ] [ 14 ]	EXPTIME-complete [ 15 ]
อาวารี[ 16 ]	12	12	32	60	3.5	[ 1 ]	การสรุปโดยทั่วไปยังไม่ชัดเจน
คิวบิก	64	30	34	20	54.2	[ 1 ]	PSPACE-complete [ 5 ]
สะพานดัมมี่คู่[ nb 1 ]	(52)	<17	<40	52	5.6		PSPACE-complete [ 17 ]
ฟาโนโรนา	45	21	46	44	11	[ 18 ]	?, แต่ในEXPTIME
มอริสเก้าคน	24	10	50	50	10	[ 1 ]	?, แต่ในEXPTIME
ตับลุต	81	27				[ 19 ]
หมากรุกสากล (10x10)	50	30	54	90	4	[ 1 ]	EXPTIME-complete [ 15 ]
หมากรุกจีน (2 ชุด)	121	23			180	[ 20 ]	EXPTIME -complete [ 21 ]
หมากรุกจีน (6 ชุด)	121	78			600	[ 20 ]	EXPTIME -complete [ 21 ]
รีเวิร์สซี่ (โอเทลโล)	64	28	58	58	10	[ 1 ]	PSPACE-complete [ 22 ]
OnTop (เกมพื้นฐานสำหรับผู้เล่น 2 คน)	72	88	62	31	23.77	[ 23 ]
แนวทางการดำเนินการ	64	23	64	44	29	[ 24 ]	?, แต่ในEXPTIME
โกโมคุ (15x15, ฟรีสไตล์)	225	105	70	30	210	[ 1 ]	PSPACE-complete [ 5 ]
หกเหลี่ยม (11x11)	121	57	98	50	96	[ 7 ]	PSPACE-complete [ 5 ]
หมากรุก	64	44	123	70	35	[ 25 ]	EXPTIME-complete (โดยไม่มีกฎการจั่ว 50 ตาเดิน ) [ 26 ]
BejeweledและCandy Crush (8x8)	64	<50			70	[ 27 ]	NP-hard
GIPF	37	25	132	90	29.3	[ 28 ]
คอนเน็กต์6	361	172	140	30	46000	[ 29 ]	PSPACE-complete [ 30 ]
แบ็กแกมมอน	28	20	144	55	250	[ 31 ]	EXPTIME-Hard (สำหรับการตั้งค่าในชีวิตจริงที่กลยุทธ์และการทอยลูกเต๋าของฝ่ายตรงข้ามไม่เป็นที่รู้จัก) [ 32 ]
เซียงฉี	90	40	150	95	38	[ 1 ] [ 33 ] [ 34 ]	?, เชื่อว่าเสร็จสมบูรณ์ตาม EXPTIME
หอยเป๋าฮื้อ	61	25	154	87	60	[ 35 ] [ 36 ]	ระดับความยาก PSPACEและในEXPTIME
ฮาวานนาห์	271	127	157	66	240	[ 7 ] [ 37 ]	PSPACE-complete [ 38 ]
ระหว่าง	572	140	159	60	452	[ 39 ]
จังกี้	90	44	160	100	40	[ 34 ]	?, เชื่อว่าเสร็จสมบูรณ์ตาม EXPTIME
ควอริดอร์	81	42	162	91	60	[ 40 ]	?, แต่ในPSPACE
คาร์กาสซอนน์ (เกมพื้นฐานสำหรับ 2 ผู้เล่น)	72	>40	195	71	55	[ 41 ]	การสรุปโดยทั่วไปยังไม่ชัดเจน
อเมซอน (10x10)	100	40	212	84	374 หรือ 299 [ 42 ]	[ 43 ] [ 44 ]	PSPACE-complete [ 45 ]
โชงิ	81	71	226	115	92	[ 33 ] [ 46 ]	EXPTIME-complete [ 47 ]
เทิร์นและแท็กซี่ (ผู้เล่น 2 คน)	33	66	240	56	879	[ 48 ]
ไป (19x19)	361	170	505	211	250	[ 1 ] [ 49 ] [ 50 ] [ 51 ]	EXPTIME-complete (โดยไม่มีกฎ superko ) [ 52 ]
อาริมา	64	43	402	92	17281	[ 53 ] [ 54 ] [ 55 ]	?, แต่ในEXPTIME
สเตรทโก	92	115	535	381	21.739	[ 56 ]
หมากรุกอนันต์	อนันต์	อนันต์	อนันต์	อนันต์	อนันต์	[ 57 ]	ไม่ทราบ แต่ mate-in- nสามารถตัดสินได้[ 58 ]
เมจิก: เดอะ แกเธอริ่ง	${\displaystyle \aleph _{0}}$	อย่างน้อย${\displaystyle \aleph _{0}}$	${\displaystyle 2^{\aleph _{0}}}$	อนันต์	อย่างน้อย${\displaystyle \aleph _{0}}$	[ 59 ] [ 60 ]	AH-hard [ 61 ]
เวิร์ดเดิล	5	4.113 (12,972)		6		[ 62 ]	ปัญหา NP-hardไม่ทราบว่าเป็นปัญหาPSPACE-completeที่มีการกำหนดพารามิเตอร์ หรือไม่

• โกะและคณิตศาสตร์
• เกมที่แก้ไขแล้ว
• การแก้ปัญหาหมากรุก
• หมายเลขแชนนอน
• รายชื่อเกมและปริศนาที่ NP-complete
• รายชื่อเกมและปริศนาครบชุดสำหรับ PSPACE

• ความซับซ้อนเชิงคำนวณของเกมและปริศนาโดยเดวิด เอปป์สไตน์