15 बिट्स में टिक-टैक-टो को एन्कोड करना
Tic-tac-toe बोर्ड को जितना संभव हो उतना संक्षेप में एन्कोड करना सूचना-सिद्धांत का एक खेल बन जाता है, जहाँ लोग सरल base-3 encodings (9 cells के लिए 15 bits) से लेकर केवल वैध, पहुँच योग्य game states गिनकर 13 bits तक की योजनाएँ खोजते हैं। अन्य लोग पूरे game histories को 20 bits से कम में एन्कोड करने या सममिति और optimal play का उपयोग करके असंभव या redundant states को छाँटने की कोशिश करते हैं, जबकि इस पर बहस भी करते हैं कि ऐसा compression कब उपयोगी है और कब बस code को जटिल बनाता है। साथ ही, thread lookup tables बनाम algorithmic encodings, perfect players विकसित करने वाले genetic algorithms, और chess, Connect-4, तथा mechanical brainteasers जैसे अधिक जटिल games और puzzles के साथ analogies को भी छूता है।
बोर्ड-स्टेट एन्कोडिंग और बिट गिनती
- मुख्य लेख एक tic‑tac‑toe बोर्ड को 9 बेस-3 अंकों में एन्कोड करता है → 15 बिट्स।
- कई टिप्पणीकार आगे की संपीड़न दिखाते हैं:
- सभी पहुँच योग्य वैध बोर्डों की गिनती 5,478 अवस्थाएँ देती है, इसलिए सममिति के बिना 13 बिट्स पर्याप्त हैं।
- एक कार्यान्वयन संयोजनों (“भरे हुए सेल्स चुनो, फिर उनमें से O चुनो”) के माध्यम से बोर्डों को [0, 6045] में एन्कोड करता है, जो 13 बिट्स में भी फिट बैठता है।
- अन्य लोग नोट करते हैं कि 765 अवस्थाओं के लिए एक भोली “10-बिट” योजना सममिति-डिडुप्लिकेटेड बोर्डों को मानती है; वास्तविक खेलों में ओरिएंटेशन (rotation/flip) के लिए अतिरिक्त बिट्स चाहिए, जिससे यह फिर लगभग 13 बिट्स तक बढ़ जाता है।
सममिति, वैधता, और किनारी मामले
- सममिति को संभालना मुश्किल है: कुछ बोर्डों को rotation+reflection को असंदिग्ध करने के लिए 3 बिट्स चाहिए, कुछ को कम, और कुछ को नहीं (पूरी तरह सममित)।
- केवल “वैध, पहुँच योग्य” बोर्डों की गिनती करना जरूरी है (टर्न क्रम का पालन करते हुए और जीत के बाद न खेलते हुए); शुरुआती स्क्रिप्टों में diagonal-win पहचान में बग थे, जिससे गिनती थोड़ी बढ़ गई थी।
- कुछ अवस्थाएँ पहुँच से बाहर हैं (दोनों खिलाड़ियों के पास winning line होना, या अलग-अलग कई wins), जिन्हें बाहर रखना चाहिए।
पूरे खेल-इतिहास की एन्कोडिंग
- पूरे play sequences को एन्कोड करने के कई तरीके:
- सरल factorial-आधारित सीमा: सभी move permutations के लिए 9! ≈ 19 बिट्स; invalid games को prune करने से केवल ~1 बिट बचता है।
- एक टिप्पणीकार सख्ती से तर्क देता है कि 18 बिट्स सभी संभावित sequences को एन्कोड नहीं कर सकते (कम-से-कम 19 चाहिए); एक और 18-बिट प्रस्ताव को “spare” bit patterns का गलत उपयोग करते हुए दिखाया जाता है।
- अन्य विचार:
- variable-length encodings जो किसी के जीतते ही रुक जाती हैं।
- सममिति का उपयोग करके पहले move विकल्पों को कम करना (corner/edge/center equivalence)।
रणनीतियाँ, AI, और मानव खेल
- minimax play पर चर्चा: optimal play कम-से-कम draw तक ले जाता है; कुछ का तर्क है कि मानव विरोधियों के लिए, non-minimax “trap-setting” अधिक बार जीत सकता है।
- ऐतिहासिक/शैक्षिक प्रणालियाँ दिखाई देती हैं: matchbox-आधारित reinforcement learner, boolean-logic strategies, सभी game states पर genetic algorithms।
प्रतिनिधित्व, lookup tables, और trade-offs
- इस पर बहस कि lookup tables “cheating” हैं या नहीं: condition chains और arrays कार्यात्मक रूप से समान हैं; solutions का मूल्यांकन data+code के कुल bits से करने का सुझाव दिया जाता है।
- कुछ लोग नोट करते हैं कि भले ही 10-bit canonical encodings मौजूद हों, practical systems convenience के लिए 13–18-bit structure में mapping table रख सकते हैं।
- trits बनाम bits पर स्पष्टता: 9 trits 15 binary bits में फिट होते हैं; किसी ternary hardware की मान्यता नहीं है।