كيف يمكنني حساب shanten عدد في ما جونغ ؟

Question

هذه هي المرة إلى في وقت سابق على سؤال حول اتخاذ قرار إذا كان يد جاهز.

معرفة قواعد جونغ تكون ممتازة لكن لعبة البوكر أو romme على أساس الخلفية هي أيضا كافية لفهم هذا السؤال.

في ما جونغ 14 البلاط (البلاط مثل البطاقات في لعبة البوكر) مرتبة إلى 4 مجموعات وزوج.على التوالي ("123") دائما يستخدم بالضبط 3 البلاط ، لا أكثر و لا أقل من ذلك.مجموعة من نفس النوع ("111") يتكون من بالضبط 3 البلاط أيضا.هذا يؤدي إلى مبلغ من 3 * 4 + 2 = 14 البلاط.

هناك العديد من الاستثناءات مثل اساسه أو ثلاثة عشر الأيتام التي لا ذات الصلة هنا.الألوان تتراوح قيمة (1-9) هي أيضا غير مهم الخوارزمية.

اليد يتكون من 13 البلاط ، كل الوقت حان دورنا نحن على اختيار بلاط جديد إلى تجاهل أي أرض من البلاط حتى نبقى على 13 البلاط - إلا إذا كان يمكننا الفوز باستخدام حديثا اختار البلاط.

اليد التي يمكن ترتيبها على شكل 4 مجموعات زوج "مستعدة".اليد التي يتطلب سوى 1 البلاط يتم تبادلها يقال "tenpai" ، أو "1 من استعداد".أي جهة أخرى لديها shanten-العدد الذي يعبر عن عدد البلاط تحتاج إلى تبادل في tenpai.حتى اليد مع shanten عدد 1 يحتاج 1 البلاط إلى tenpai (2 البلاط أن يكون مستعدا لذلك).اليد مع shanten عدد 5 يحتاج 5 البلاط إلى tenpai وهلم جرا.

أحاول حساب shanten عدد من يده.بعد غوغلينغ حول لساعات و قراءة مقالات متعددة ورقات عن هذا الموضوع, هذا يبدو أن المشكلة لم تحل (باستثناء القوة الغاشمة النهج).أقرب خوارزمية يمكن أن تجد تعتمد على الصدفة ، أيفإنه لم يكن قادرا على كشف الصحيح shanten عدد 100 ٪ من الوقت.

القواعد

سأشرح قليلا عن قواعد الفعلية (المبسطة) ثم فكرتي كيفية التعامل مع هذه المهمة.في ما جونغ ، هناك 4 ألوان ، 3 تلك العادية مثل الألعاب بطاقة (ace, قلب, ...) التي تسمى "رجل", "دبوس" و "سو".هذه الألوان من 1 إلى 9 في كل و يمكن استخدامها على شكل المستقيمة وكذلك مجموعات من نفس النوع.عليها اللون يسمى "الشرف" و يمكن أن تستخدم مجموعات من نفس النوع فقط ، ولكن ليس المستقيمة.سبعة يكرم سوف يطلق "E, S, W, N, R, G, B".

دعونا ننظر في مثال tenpai اليد: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E.نحن المقبل اختيار E.هذا هو استكمال جونغ اليد (جاهزة) و يتكون من 2-4 دبوس شارع (تذكر, دبابيس يمكن استخدامها المستقيمة) 3 دبوس الثلاثي ، 5 man triple a W الثلاثي و ه زوج.

تغيير الأصلية اليد قليلا 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, لدينا يد في 1-shanten ، أيفإنه يتطلب بلاط إضافية إلى tenpai.في هذه الحالة, تبادل 2p على 3p يعيدنا إلى tenpai ذلك عن طريق رسم 3p و ه علينا الفوز.

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W هو من ناحية في 2-shanten.هناك 1 اكتمل الثلاثي و 5 أزواج.نحن بحاجة إلى زوج واحد في النهاية ، لذلك بمجرد اختيار واحد من 1p, 5p, 9p ، ق أو ث نحن بحاجة إلى التخلص من واحد من أزواج أخرى.على سبيل المثال:نختار الرقم 1 و تجاهل دبليواليد في 1-shanten الآن يبدو مثل هذا: 1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W.المقبل, ننتظر إما 5p, 9p أو إس.على افتراض أننا اختيار 5p والتخلص من بقايا W, حصلنا على هذا: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S.هذا من ناحية ومن في tenpai في إكمال إما على 9 دبوس أو إس.

لتجنب رسم هذا النص في طول حتى أكثر من ذلك ، يمكنك الاطلاع على المزيد سبيل المثال في ويكيبيديا أو استخدام واحدة من العديد من نتائج البحث في جوجل.كل منهم أكثر قليلا التقنية على الرغم من ذلك أتمنى أن الوصف أعلاه يكفي.

خوارزمية

كما جاء أود لحساب shanten عدد من يده.كانت فكرتي أن تقسيم البلاط إلى 4 مجموعات حسب اللون.التالي, كل البلاط يتم فرزها في مجموعات داخل مجموعاتهم إلى أننا في نهاية المطاف إما مع ثلاثة توائم, أزواج أو البلاط واحد في مجموعة شرف أو, بالإضافة إلى ذلك, streights في 3 العادي المجموعات.الانتهاء من مجموعات يتم تجاهل.أزواج تحسب من العدد النهائي هو decremented (نحتاج 1 زوج في النهاية).واحدة البلاط تضاف إلى هذا الرقم.أخيرا, نقسم العدد 2 (لأن في كل مرة نختار جيدة البلاط الذي يقربنا إلى tenpai يمكننا التخلص من آخر غير المرغوب فيها البلاط).

إلا أنني لا يمكن أن تثبت أن هذه الخوارزمية هو الصحيح, و أنا أيضا لدي مشكلة في دمج المستقيمة صعبة المجموعات التي تحتوي على العديد من البلاط في مسافة قريبة.كل نوع من الفكرة هو موضع تقدير.أنا النامية في .صافي ولكن البرمجية الزائفة أو أي قراءة لغة هو موضع ترحيب أيضا.

Answer 1

لقد فكرت في هذه المشكلة أكثر قليلا.لمعرفة النتائج النهائية ، انتقل إلى القسم الأخير.

الفكرة الأولى:القوة الغاشمة النهج

أولا أنا كتبت نهج القوة الغاشمة.كان قادرا على التعرف 3-shanten في غضون دقيقة ، لكنه لم يكن موثوقة جدا (في بعض الأحيان وقتا أطول ، تعداد الفضاء كله من المستحيل حتى بالنسبة فقط 3-shanten).

تحسين القوة الغاشمة النهج

الشيء الوحيد الذي يتبادر إلى الأذهان أن أضيف بعض المعلومات على القوة الغاشمة النهج.ساذج هو طريقة لإضافة أي من البلاط المتبقية ، انظر إذا أنتجت جونغ, و إن لم يكن محاولة متكرر حتى تم العثور عليها.على افتراض أن هناك حوالي 30 البلاط مختلفة اليسار و أقصى عمق 6 (لست متأكدا إذا كان 7+-shanten اليد بل هو ممكن [تحرير:وفق الصيغة التي وضعت في وقت لاحق ، أقصى حد ممكن shanten رقم (13-1)*2/3 = 8]) نحصل على (13*30)^6 الاحتمالات التي هي كبيرة (10^15 مجموعة).

ومع ذلك ، هناك حاجة لوضع كل بقايا البلاط في كل موقف في يدك.لأن كل لون له أن يكون كاملا في نفسه ، يمكننا إضافة البلاط كل لون والجماعات ملاحظة إذا كانت المجموعة كاملة في حد ذاته.تفاصيل مثل وجود بالضبط 1 زوج عموما ليست صعبة إلى إضافة.هذا الطريق ، وهناك ماكس حول (13*9)^6 الاحتمالات ، أن حوالي 10^12 و أكثر جدوى.

أفضل حل:تعديل القائمة جونغ مدقق

التالي فكرة استخدام رمز كتبت المبكر لاختبار جونغ وتعديله بطريقتين:

• لا تتوقف عند غير صالحة اليد العثور عليها ولكن ملاحظة أسفل البلاط في عداد المفقودين
• إذا كان هناك عدة طرق يمكن استخدام البلاط ، جرب كل منهم

هذا ينبغي أن يكون الأمثل الفكرة مع بعض ارشادي وأضاف أنه ينبغي أن يكون الأمثل الخوارزمية.إلا أنني وجدت أنه من الصعب جدا تنفيذ - من الممكن بالتأكيد على الرغم من.أنا أفضل أسهل في الكتابة والحفاظ على الحل الأول.

متقدمة النهج باستخدام مجال المعرفة

التحدث مع أكثر من لاعب من ذوي الخبرة ، يبدو أن هناك بعض القوانين التي يمكن استخدامها.على سبيل المثال, مجموعة من البلاط 3 لا تحتاج إلى أن تكون مكسورة ، كما أنه لن ينخفض shanten عدد.بيد أنه قد يكون استخدامها بطرق مختلفة (مثلا ، 111 أو 123 الجمع).

تعداد كل شيء ممكن 3-مجموعة إنشاء محاكاة جديدة لكل منهم.إزالة 3-مجموعة.الآن إنشاء كل 2-تعيين في الناتج اليد ومحاكاة كل أرض من البلاط التي يحسن بها 3-مجموعة.في نفس الوقت, محاكاة لأي من 1-مجموعات يتم إزالتها.نواصل القيام بهذا حتى كل 3 - و 2-مجموعات ولت.يجب أن يكون هناك 1-مجموعة (وهذا هو ، واحد البلاط) أن يترك في نهاية المطاف.

تعلمه من تنفيذ خوارزمية النهائية

انا تنفيذ الخوارزمية المذكورة أعلاه.لتسهيل فهم كتبته في شبة الكود:

Remove completed 3-sets
If removed, return (i.e. do not simulate NOT taking the 3-set later)

Remove 2-set by looping through discarding any other tile (this creates a number of branches in the simulation)
If removed, return (same as earlier)

Use the number of left-over single tiles to calculate the shanten number

بالمناسبة, هذا هو في الواقع مشابهة جدا النهج آخذ عند حساب عدد نفسي ، و من الواضح أبدا أن ينتج عالية جدا عدد.

هذا يعمل بشكل جيد جدا على جميع الحالات تقريبا.ومع ذلك ، وجدت أنه في بعض الأحيان في وقت سابق افتراض ("إزالة أنجزت بالفعل 3-مجموعات ابدأ فكرة سيئة") خطأ.لمكافحة سبيل المثال: 23566M 25667P 159S.الجزء المهم هو 25667.قبل إزالة 567 3-مجموعة نحن في نهاية المطاف مع اليسار أكثر 6 البلاط ، مما يؤدي إلى 5-shanten.سيكون من الأفضل استخدام اثنين من البلاط واحد على شكل 56x و 67x, ، مما يؤدي إلى 4-shanten العام.

إلى إصلاح ، ونحن بسيطة لإزالة الخطأ الأمثل ، مما يؤدي إلى هذا الكود:

Remove completed 3-sets
Remove 2-set by looping through discarding any other tile
Use the number of left-over single tiles to calculate the shanten number

وأعتقد أن هذا دائما بدقة يجد أصغر shanten عدد لكني لا أعرف كيف تثبت ذلك.الوقت المستغرق في نطاق "معقول" (على آلة 10 ثانية كحد أقصى ، وعادة 0 ثانية).

النقطة الأخيرة هو حساب shanten من عدد من الأيسر على واحدة من البلاط.أولا وقبل كل شيء ، فمن الواضح أن العدد هو في شكل 3*n+1 (لأننا بدأت مع 14 البلاط دائما تطرح 3 البلاط).

إذا كان هناك 1 البلاط اليسار ، نحن shanten بالفعل (نحن فقط في انتظار النهائي زوج).مع البلاط 4 اليسار إلى تجاهل 2 منهم لتشكيل 3-تعيين ، وترك لنا مع البلاط واحد مرة أخرى.وهذا يؤدي إلى 2 إضافية المرتجع.مع 7 البلاط لدينا 2 مرات 2 المرتجع ، إضافة 4.وهلم جرا.

وهذا يؤدي إلى معادلة بسيطة shanten_added = (number_of_singles - 1) * (2/3).

وصف الخوارزمية يعمل بشكل جيد و اجتاز كل الاختبارات ، لذا أفترض أنه هو الصحيح.كما ذكرت لا أستطيع إثبات ذلك على الرغم من.

منذ خوارزمية يزيل الأرجح البلاط مجموعات الأولى, ذلك النوع من لديه المدمج في التحسين.إضافة فحص بسيط if (current_depth > best_shanten) then return; أنه يعمل بشكل جيد جدا حتى عالية shanten الأرقام.

Answer 2

اعتقد ان A* من وحي النهج.تحتاج إلى العثور على بعض مجريات الأمور التي لا يغالي shanten عدد واستخدامه للبحث القوة الغاشمة شجرة فقط في المناطق حيث أنه من الممكن أن ندخل في استعداد الدولة بسرعة كافية.

Answer 3

الصحيح خوارزمية العينة: syanten.cpp

عودي قطع أشكال من ناحية بالترتيب:مجموعات, أزواج, أشكال غير مكتملة و الاعتماد عليه.في كل الاختلافات.و النتيجة هي الحد الأدنى Shanten قيمة جميع المتغيرات:Shanten = Min(Shanten, 8 - * 2 - - )

C# نموذج (rewrited من c++) يمكن العثور عليها هنا (باللغة الروسية).

Answer 4

لقد فعلت قليلا من التفكير و جاء مع مختلف قليلا صيغة من جمعية بيوت الشباب الكندية ؟ أولا النظر في اليد (فظيع جدا اليد):

1s 4s 6s 1m 5m 8m 9m 9m 7p 8p غرب شرق شمال

باستخدام جمعية بيوت الشباب الكندية خوارزمية كل ما يمكننا فعله هو يلقي بها زوج (9 ، 9).ثم نحن مع اليسار 11 الفردي.الآن لو طبقنا جمعية بيوت الشباب الكندية صيغة نحصل على (11-1)*2/3 الذي هو ليس عدد صحيح وبالتالي لا يمكن أن يكون shanten عدد.هذا هو المكان الذي جاء مع هذا:

ن = ( (S + 1) / 3 ) - 1

ن تقف على shanten رقم S لدرجة المبلغ.ما هي النتيجة ؟ إنه عدد من البلاط تحتاج إلى إجراء مجموعة كاملة كاملة.على سبيل المثال, إذا كان لديك (4,5) في يدك أنت تحتاج إما 3 أو 6 لجعلها كاملة 3-تعيين هذا هو واحد فقط من البلاط.لذلك هذا غير مكتملة الزوج يحصل على درجة 1.وفقا لذلك, (1,1) يحتاج فقط 1 لتصبح 3-مجموعة.أي البلاط واحد ومن الواضح أن احتياجات 2 البلاط لتصبح 3-تعيين ويحصل على درجة 2.أي مجموعة كاملة بالطبع الحصول على النتيجة 0.علما أن نتجاهل إمكانية الفردي أصبحت أزواج.الآن لو كنا في محاولة للعثور على جميع ناقصة مجموعات في أعلاه نحصل على:

(4s ، 6s) (8 ، 9) (7p,8p) 1s 1m 5m 9m غرب شرق شمال

ثم نحسب مجموع الدرجات = 1*3+2*7 = 17.الآن لو طبقنا هذا العدد إلى الصيغة أعلاه نحصل على (17+1)/3 - 1 = 5 مما يعني أن هذه اليد 5-shanten.أنها إلى حد ما أكثر تعقيدا من أليكسي و ليس لدي دليل ولكن حتى الآن لا يبدو أن العمل بالنسبة لي.علما أن مثل هذه اليد يمكن أن يكون تحليل في طريقة أخرى.على سبيل المثال:

(4s ، 6s) (9 ، 9) (7p,8p) 1s 1m 5m 8m غرب شرق شمال

ومع ذلك, فإنه لا يزال يحصل على درجة مبلغ 17 5-shanten وفقا الصيغة.أنا أيضا لا دليل على هذا و هذا هو قليلا أكثر تعقيدا من أليكسي صيغة ولكن أيضا يقدم الدرجات التي يمكن تطبيقها(?) إلى شيء آخر.

Answer 5

تحديد ما إذا كانت يدك بالفعل في tenpai يبدو متعدد حقيبة المشكلة.الجشع خوارزميات لن تعمل - كما Dialecticus أشار إلى ذلك, سوف تحتاج إلى النظر في المشكلة برمتها في الفضاء.