SplitCircuit: سولور اور خودکار کھلاڑی والا ایک پزل پروٹوٹائپ
مارچ کے شروع میں میں نے Unity میں SplitCircuit بنایا، سیڈ پر مبنی ایک چھوٹا پزل پروٹوٹائپ۔ تقریباً 29 گھنٹوں میں دس کمٹس اسے ایک خالی ریپوزٹری سے یہاں تک لے گئیں:
- ایک قابلِ کھیل گیم لوپ، جس کا مرکز خالص ڈیٹا ہے اور ہر ذیلی نظام کا اپنا سیڈ ہے؛
- ایک brute-force سولور جو رینڈرر کے بغیر گیم کھیلتا ہے؛
- ایک سیڈ اسکینر، اور ایڈٹ موڈ ٹیسٹ جو سولور کو دو بار چلا کر یکساں جوابات کا تقاضا کرتے ہیں؛
- ایک لامتناہی رنر جو بے ترتیب پزلز پہلے سے حل کرتا ہے اور پھر انہیں اصل گیم کے ذریعے، نظر آنے والے انداز میں، مسلسل دوبارہ چلاتا ہے۔
یہ آخری حصہ WebGL بلڈ کے طور پر لائیو ہے۔ آپ اسے یہاں خود کو کھیلتے دیکھ سکتے ہیں: SplitCircuit لامتناہی خودکار رن ڈیمو۔
| کمٹ | کیا شامل ہوا | حجم |
|---|---|---|
6bbd3a2 | پروف آف کانسیپٹ: بورڈ، کٹ، نَج، سیٹل، سرکٹ چیک | 154 فائلیں، +11,051 |
6a8d79e | سولور، پلے بیک، سیڈ اسکینر، ٹیسٹ انفراسٹرکچر | 48 فائلیں، +2,679 / -51 |
6dba7d7 | پلے بیک اب لائیو بورڈ کے مقابل راؤنڈ بہ راؤنڈ حل کرتا ہے | 3 فائلیں، +147 / -110 |
53e7a66 | لامتناہی رنر، چار پری سیٹس، ہر پری سیٹ کے لیے ایک کلک میں WebGL بلڈ | 21 فائلیں، +1,725 / -539 |
کوڈ AI کوڈنگ ایجنٹس نے میرے ڈیزائن اور رولز فائل کی بنیاد پر لکھا؛ پابندیاں میں نے طے کیں، ہر قدم کا جائزہ میں نے لیا اور اگلا قدم میں نے طے کیا۔ یہ تحریر ڈیزائن کے فیصلوں کے بارے میں ہے، کیونکہ انہی کی وجہ سے خودکار کھلاڑی بنانا سستا پڑا۔
گیم
گرڈ کے بیچ میں ایک polyomino نمودار ہوتا ہے۔ آپ اسے ایک عمودی اور ایک افقی کٹ سے چار ٹکڑوں میں کاٹتے ہیں۔ ٹکڑے باہر کی طرف سرکتے ہیں، ہر ایک ایک کنارے کی طرف، ہر tick پر ایک خانہ۔ tick کے درمیان آپ انہیں پہلو کی طرف نَج کر سکتے ہیں، مگر کنٹرولز الٹے جڑے ہوئے ہیں: اوپر دبانے سے دایاں ٹکڑا اوپر اور بایاں ٹکڑا نیچے جاتا ہے۔ کوئی ٹکڑا کنارے سے یا پچھلے راؤنڈز میں جمے ہوئے مواد سے ٹکرا کر رک جاتا ہے، Tetris کی طرح، اور بورڈ کا مستقل کنڈکٹو حصہ بن جاتا ہے۔
ہر سیٹل کے بعد گیم Start نوڈ سے breadth-first سرچ چلاتی ہے۔ اگر وہ End نوڈ تک پہنچ جائے تو سرکٹ مکمل ہے اور آپ جیت گئے۔ اگر کوئی ٹکڑا ایک قدم بھی آگے نہ بڑھ سکے، یا بیچ کا حصہ اتنا بھرا ہو کہ اگلی شکل نہ بن سکے، تو آپ ہار گئے۔
دو اصول جنہوں نے باقی سب کی قیمت ادا کی
پروجیکٹ کی رولز فائل نے، کسی بھی سولور کے وجود سے پہلے، دو پابندیاں طے کیں:
- خالص ڈیٹا کا مرکز۔
BoardState،CutResult،FragmentStateاورRouteResultسادہ C# کلاسز ہیں جن میں کوئیMonoBehaviourنہیں۔ رینڈرر اور گیم مینیجر ان کے اوپر بیٹھتے ہیں۔ - ڈیٹرمنسٹک سیڈز۔ تمام جنریشن اور سمولیشن واضح سیڈز کے ساتھ
System.Randomاستعمال کرتی ہے، کبھیUnityEngine.Randomنہیں۔ شکل، رنگ، Start/End کی جگہ، ریلے اور پہلے سے رکھی تاروں کا ہر ایک کا اپنا سیڈ ہے، اس لیے ایک بدلنے سے باقی نہیں بکھرتے۔ بعد کے راؤنڈز اپنی شکلیں شکل کے سیڈ اور راؤنڈ نمبر سے اخذ کرتے ہیں۔
یہی دو انتخاب وجہ ہیں کہ سولور ایک دن کا کام بنا، دوبارہ لکھائی نہیں۔ سولور بورڈ بنا سکتا ہے، کٹ لگا سکتا ہے، فریگمنٹ سمولیٹر چلا سکتا ہے اور سرکٹ ہزاروں بار چیک کر سکتا ہے، کسی سین کو چھوئے بغیر۔ اور چونکہ اگلی شکل سیڈ والے جنریٹر سے آتی ہے، سولور بالکل وہی شکل بنا سکتا ہے جو اصل گیم اگلی بار بنائے گی۔ سولور میں موجود تبصرہ یہ بات سیدھے لفظوں میں کہتا ہے: "Spawn next shape (mirroring GameManager's RNG progression)"۔
سولور کیسے تلاش کرتا ہے
6a8d79e کا سولور جان بوجھ کر سادہ ہے: ایک راؤنڈ کے اندر مکمل تلاش، راؤنڈز کے درمیان
greedy۔
ایک راؤنڈ کے لیے یہ ہر جائز کٹ آزماتا ہے۔ 16 ضرب 16 کے بورڈ پر یہ 14 عمودی پوزیشنز ضرب 14 افقی پوزیشنز، یعنی 196 کٹس ہیں۔ ہر کٹ کے لیے یہ پہلے جانچتا ہے کہ ہر نَج محور ٹکڑوں کے ٹکرانے سے پہلے کتنا ہل سکتا ہے، پھر ان حدود کے اندر ہر عمودی اور افقی نَج آفسیٹ آزماتا ہے، ٹکڑوں کو رکنے تک سمولیٹ کرتا ہے، اور سرکٹ چیک کرتا ہے۔
for vCut in 1 .. width-2
for hCut in 1 .. height-2
probe nudge bounds for this cut
for vNudge in minV .. maxV
for hNudge in minH .. maxH
simulate settle, check circuit
اگر کوئی امتزاج اسی راؤنڈ میں سرکٹ مکمل کر دے تو یہ اسے لے لیتا ہے۔ اگر کوئی نہ کرے تو یہ ہر امتزاج کو ایک heuristic سے اسکور دیتا ہے اور بہترین رکھتا ہے:
- فاصلہ (غالب)۔ Start سے اور End سے کنڈکٹو خانوں میں الگ الگ breadth-first سرچ چلائیں۔ اسکور دونوں قابلِ رسائی مجموعوں کے درمیان سب سے کم Manhattan فاصلہ ہے، جس کا وزن 100,000 ہے۔ اس فاصلے کو ختم کرنا ہی پوری گیم ہے۔
- اسپان کی جگہ کا خالی ہونا (ثانوی)۔ بیچ کے اسپان علاقے کا وہ حصہ جو ابھی خالی ہے، وزن 100۔ جو چال فاصلہ تو کم کرے مگر بیچ کو بند کر دے، وہ دو راؤنڈ بعد ہار جاتی ہے۔
- قابلِ رسائی حجم (فیصلہ کن)۔ جتنا زیادہ جڑا ہوا مواد، اتنا بہتر۔
پھر یہ منتخب قدم لاگو کرتا ہے، سیڈ والے جنریٹر سے اگلی شکل بناتا ہے، اور دہراتا ہے جب تک
جیت نہ جائے، جائز چالیں ختم نہ ہو جائیں، بیچ بند نہ ہو جائے، یا راؤنڈ کی حد نہ آ جائے۔ ہر
نتیجے میں ایک اسٹیٹس (Solved، Unsolvable، MaxRoundsReached)، اٹھائے گئے قدم، جانچے
گئے امتزاجات کی تعداد اور لگا ہوا وقت ہوتا ہے۔
یہ greedy ہے، اس لیے بہترین نہیں، اور یہ کسی قابلِ حل پزل کو ناقابلِ حل کہہ سکتا ہے۔ ایک پروٹوٹائپ کے لیے یہی درست سودا ہے: اسے سمجھنا آسان ہے، اور جو سوال یہ جواب دیتا ہے ("کیا ایک معقول کھلاڑی یہ سیڈ مکمل کر سکتا ہے؟") وہی ہے جس کی پزل ڈیزائنر کو ضرورت ہے۔
یہ ثابت کرنا کہ یہ ڈیٹرمنسٹک ہے
ایڈٹ موڈ ٹیسٹس میں ایک ٹیسٹ ایک ہی کنفیگریشن پر سولور کو دو بار چلاتا ہے اور تصدیق کرتا ہے کہ اسٹیٹس، قدموں کی تعداد اور ہر قدم یکساں ہیں۔ یہ چھوٹا سا ٹیسٹ ہے، مگر یہی سولور کو ایماندار رکھتا ہے: اگر جنریشن یا سمولیشن میں کوئی چیز بغیر سیڈ کے بے ترتیب ذریعے یا فریم پر منحصر قدر کو پڑھنے لگے، تو دونوں رن مختلف ہوں گے اور ٹیسٹ فیل ہو جائے گا۔
اسی کمٹ نے ایک سیڈ اسکینر بھی شامل کیا (ایک ایڈیٹر پینل، ایک مینو رنر اور ایک ٹیسٹ یوٹیلٹی) جو سیڈز کی ایک رینج کو چھانتا ہے اور بتاتا ہے کہ سولور کون سے مکمل کر سکتا ہے، اور ساتھ ایک PowerShell بیچ موڈ ٹیسٹ رنر جو Unity کے XML نتائج کو JSON میں بدلتا ہے۔
سولور سے خودکار کھلاڑی تک
پلے بیک کا پہلا ورژن پورا پزل میموری میں حل کرتا تھا، اور صرف تبھی دوبارہ چلاتا تھا جب پورا حل کامیاب ہو۔ ناکامی پر آپ کو کچھ نظر نہیں آتا تھا اور بورڈ کی کوئی تصویر نہیں ملتی تھی، جبکہ ٹھیک اسی وقت آپ سب سے زیادہ دیکھنا چاہتے ہیں۔
6dba7d7 نے ڈھانچہ بدل دیا: پلے بیک اب اصل GameManager بورڈ کے مقابل سولور سے ایک وقت
میں ایک قدم مانگتا ہے، پھر اسکرین پر اصل کٹ، نَج، tick اور سیٹل کا عمل چلاتا ہے۔ نتیجہ
کچھ بھی ہو، ہر راؤنڈ نظر آتا ہے اور محفوظ ہوتا ہے۔ اسی کمٹ نے فریگمنٹ سمولیٹر میں جانچ کی
ترتیب بھی بدلی، تاکہ کنارے تک پہنچنے کی جانچ سے پہلے ہر خانے کے لیے جمے ہوئے مواد سے
ٹکراؤ جانچا جائے، جس سے کوئی ٹکڑا کنارے پر پڑے ذخیرے پر چڑھ نہیں پاتا۔ رولز فائل یہ ترجیح
پہلے سے بیان کرتی تھی؛ اب کوڈ اس کے مطابق ہو گیا۔ کمٹ کی تاریخ یہ نہیں بتاتی کہ یہ فرق کیسے
پکڑا گیا، اس لیے میں یہ دعویٰ نہیں کروں گا کہ خودکار کھلاڑی نے اسے ڈھونڈا۔
لامتناہی رنر
آخری کمٹ نے کام کو دو coroutines میں بانٹ دیا:
- پہلے سے حل۔ 10 پزلز کی ایک قطار رکھیں۔ کسی پری سیٹ سے بے ترتیب کنفیگریشن بنائیں، اس پر greedy سولور چلائیں (زیادہ سے زیادہ 50 راؤنڈ)، اور نتیجہ قطار میں ڈالیں۔ یہ خالص ڈیٹا ہے اور کبھی سین کو نہیں چھوتا۔
- پلے بیک۔ اگلا پزل لیں، بیرونی کنٹرول میں ایک نیا
GameManagerبنائیں، اور سولور کے قدم اس کے ذریعے دوبارہ چلائیں: کٹ سیٹ کریں، تصدیق کریں، نَج لگائیں، اور tick آگے بڑھاتے رہیں جب تک سب کچھ جم نہ جائے۔
جس ڈیزائن فیصلے کی مجھے سب سے زیادہ پروا ہے وہ یہ ہے کہ ایک گیم کا اسکور کیسے ہوتا ہے۔ رنر
سولور کے اسٹیٹس پر بھروسہ نہیں کرتا۔ وہ کسی گیم کو صرف تبھی حل شدہ گنتا ہے جب لائیو
GameManager اپنے Complete مرحلے پر ختم ہو۔ سولور اور گیم ایک ہی بنیادی کلاسز استعمال
کرتے ہیں، مگر پلے بیک کا راستہ گیم کی اپنی اسٹیٹ مشین، ان پٹ کے داخلی راستوں اور اسپاننگ
سے گزرتا ہے۔ اگر دونوں کبھی متفق نہ ہوں تو اسکرین پر حل شدہ اور ناکام گیمز کا کاؤنٹر یہ
دکھا دے گا، اور ہر گیم اپنا نتیجہ اپنے بورڈ اسنیپ شاٹس اور ہر tick کی تصاویر کے ساتھ لکھتا
ہے۔
چار پری سیٹس ہیں (Checkers، Chess، Go اور Full Random) جو بورڈ کا سائز، شکل کے جنریٹرز، رنگوں کی تقسیم اور Start/End کی جگہ بدلتے ہیں۔ ایک ایڈیٹر ٹول ہر پری سیٹ کے لیے ایک سین بناتا ہے اور ہر ایک کو ایک ہی قدم میں WebGL میں بلڈ کرتا ہے۔ اوپر دیا گیا ڈیمو Full Random پری سیٹ ہے۔ یہ ہر گیم کے لیے نئے سیڈز لیتا ہے، اس لیے ہر بار آنے پر مختلف پزلز نظر آتے ہیں؛ ایک گیم کے اندر سب کچھ اس کے سیڈز سے طے ہوتا ہے۔
جنریٹر کی حفاظتی حدود
جب لامتناہی رنر بن رہا تھا، بورڈ جنریٹر میں تین اصول شامل ہوئے، ہر ایک پر تبصرے میں اسے guardrail کہا گیا ہے:
- Start اور End کو اسپان علاقے سے کم از کم ایک خانہ دور ہونا چاہیے، "otherwise fragments can't move and it's an instant loss" (ورنہ ٹکڑے ہل نہیں سکتے اور فوری ہار ہوتی ہے)۔
- Start اور End کبھی سیدھے پڑوسی نہیں ہونے چاہییں، ورنہ پزل پہلے سے حل شدہ ہوگا۔
nخانوں والی شکل کے لیے فی ٹکڑا کم از کم خانوں کی حد(n - 1) / 4تک محدود ہے، تاکہ ایک جائز چار حصوں والا کٹ ہمیشہ موجود ہو۔
کمٹس اصول درج کرتی ہیں، یہ نہیں کہ انہیں کس چیز نے جنم دیا، اس لیے میں انہیں ویسے ہی پیش کرتا ہوں جیسے وہ ہیں: ایسی پابندیاں جو ہر بنائے گئے بورڈ کو ایک حقیقی پزل بناتی ہیں۔
جو بات عام طور پر لاگو ہوتی ہے
پہلے دن سے مرکز کو خالص اور بے ترتیبی کو سیڈ والا رکھیں۔ دونوں میں سے کوئی اصول سولور کے لیے نہیں لکھا گیا تھا۔ انہی کی وجہ سے سولور، ڈیٹرمنزم ٹیسٹ اور خود کھیلنے والا ڈیمو ایک مختصر اگلا قدم بنے، کوئی ری فیکٹر نہیں۔
بوٹ کو اصل گیم کھیلنے دیں۔ جو سولور صرف اپنا ماڈل جانچتا ہے وہ ہمیشہ اپنے آپ سے متفق رہ سکتا ہے۔ اس کی چالوں کو اصل گیم لوپ کے ذریعے دوبارہ چلانا، اور گیم کی اپنی اختتامی حالت سے اسکور کرنا، دونوں کو ایک دوسرے کی جانچ پر لگا دیتا ہے۔
ناکامی کو سب سے نمایاں صورت بنائیں۔ پہلا پلے بیک صرف کامیابیاں دکھاتا تھا۔ حل یہ تھا کہ لائیو بورڈ کے مقابل ایک وقت میں ایک راؤنڈ حل کیا جائے، تاکہ ناکام سیڈ سب سے زیادہ ثبوت پیدا کرے، سب سے کم نہیں۔