Struktur Data untuk Permainan Logika / Aturan Pengurangan / Kumpulan Petunjuk yang Cukup?

11

Saya telah memikirkan mengembangkan game logika yang mirip dengan Einstein Puzzle , yang akan memiliki set petunjuk yang berbeda untuk setiap replay game baru.

Struktur data apa yang akan Anda gunakan untuk menangani entitas yang berbeda (hewan peliharaan, warna rumah, kebangsaan, dll.), Aturan deduksi, dll. Untuk menjamin bahwa petunjuk yang Anda berikan menunjukkan solusi unik?

Saya mengalami kesulitan memikirkan bagaimana cara mendapatkan aturan deduksi untuk bermain bersama dengan kemungkinan petunjuk; wawasan apa pun akan dihargai.

logic data-structure puzzle taserian
sumber
1
Saya tidak berpikir itu akan sangat menarik untuk dimainkan. Setelah Anda menyelesaikannya sekali , melakukannya lagi dengan aturan yang berbeda tidak akan jauh berbeda dari bermain sudoku.
o0 '.
4
Di sisi lain, orang melakukan ratusan sudoku sebelum bosan dengan mereka. Dan jika Anda mengikat jawaban untuk beberapa aksi di dunia daripada hanya mengetikkan angka atau nama, orang bahkan tidak akan mengeluh itu sudoku.
Ini mengingatkan saya pada game ini: nick.com/games/series.html
CeeJay
3
Saya sarankan untuk melihat permainan Everett Kaser - dia telah membuat banyak permainan seperti ini, khususnya Sherlock yang terinspirasi oleh teka-teki itu, tetapi juga beberapa game lain, seperti Honeycomb Hotel atau game terbarunya , Ny . Hudson . Mungkin membantu Anda untuk melihat hal semacam ini beraksi.
Michael Madsen
@ Jo: apa yang Anda katakan itu benar secara teknis, tetapi yang penting di sini adalah mengetahui apa yang sedang Anda lakukan. Melakukan permainan seperti sudoku baik-baik saja jika Anda sadar Anda melakukan itu, sementara itu hampir pasti akan menghasilkan hasil omong kosong jika Anda berpikir Anda melakukan sesuatu yang lain.
o0 '.

Jawaban:

4

Wow. Ini sebenarnya tampak seperti situasi di mana web semantik AI sekolah lama, seperti yang menurut Richard Bartle akan penting bagi masa depan game ketika ia menulis Artificial Intelligence dan Computer Games , akan bermanfaat. Anda pada dasarnya memiliki beberapa daftar data (tabel database, apa pun), yang pertama menentukan aturan tentang bagaimana hal-hal dapat saling berhubungan, seperti:

a PERSON must LIVE IN a DOMICILE
a PERSON must OWN an ANIMAL
a PERSON must DRINK a BEVERAGE
a PERSON must SMOKE a CIGARETTE BRAND
a PERSON must BE OF a NATIONALITY
a DOMICILE must BE IN a POSITION
a DOMICILE must BE OF a COLOR

Maka Anda memiliki contoh kategori:

ANIMAL: dog snail zebra fox horse
BEVERAGE: milk tea OJ coffee water
CIGARETTE BRAND: Kools Parliaments Luckies OldGold Chesterfields
NATIONALITY: Englishman Spaniard Ukrainian Japanese Norwegian
POSITION: first second third fourth fifth
COLOR: red green yellow ivory blue

Struktur data ini tidak sepenuhnya merangkum situasi - Anda memerlukan batasan keunikan, dan beberapa kategori memerlukan meta-rules, seperti POSITIONpenanganan kebutuhan "di sebelah kanan", "di sebelah kiri", dan "berikutnya untuk "konsep, misalnya - tetapi struktur masalah tampaknya sangat menyarankan mereka.

Tidak tahu apakah ini akan membawa Anda terlalu jauh, tapi saya harap ini membantu.

kekacauan
sumber
4

Rekomendasi saya adalah melihat kode Python untuk Constraint Satisfaction Problems (CSPs) yang disediakan dengan proyek AIMA . Mereka menggunakan Kamus (array asosiatif / tabel hash) untuk melacak kendala yang valid. Juga, ada implementasi dari beberapa algoritma yang digunakan untuk menyelesaikan CSP, seperti konflik kecil dan AC3.

Kode termasuk contoh masalah Zebra sebagai contoh, seperti yang Anda tautkan.

Brandon
sumber
1

Ini sebenarnya sangat dalam. Aneh bahwa Wikipedia tidak pernah menyebutkannya.

Apa yang Anda cari adalah bukti yang sangat sulit yang mungkin, bisa dicapai dengan hal-hal seperti bukti Fitch . Jadi kami mencoba untuk mengurangi hal-hal dari data yang kami berikan. Ada banyak pembangun bukti Fitch yang melakukan banyak pekerjaan untuk Anda. Tetapi beberapa latihan tidak membuktikan.

Saya tidak tahu apakah pengguna harus melakukan perhitungan. Jika demikian, perhatikan hal-hal seperti 3SAT , yang merupakan masalah yang tidak dapat diatasi untuk waktu polinomial.

Adapun struktur data yang ingin Anda gunakan, saya pikir Anda ingin memiliki semacam Rulekelas. Aturannya bisa apa saja, tergantung jenisnya. Tidak ada banyak aturan dalam logika predikat , jadi ini bisa diatasi dengan mewarisi (jika, iff, dan, atau, tidak ...). Aturan-aturan ini hanya perlu dievaluasi. Dan satu-satunya hal yang dapat dilakukan aturan, adalah mengembalikan benar atau salah. Karena itulah yang Anda lakukan dengan predikat logika. Di universitas, saya direkomendasikan untuk membaca buku ini oleh John Kelly .

Kembali ke kelas: Anda akan melihat masalah-masalah ini seperti yang Anda lihat menerapkan perhitungan normal dengan matematika. Apa itu +operator? Ini berisi dua parameter, yang bisa berupa persamaan baru dengan sendirinya, atau hanya angka. Saya pikir Anda memiliki hal yang sama dengan Aturan. Mereka dapat memiliki Aturan baru sebagai parameter, atau hanya boolean (disebut predikat).

Saya harap ini banyak membantu Anda, terutama referensi. Jika Anda ingin tahu lebih banyak, atau jika saya pergi ke arah yang salah, tolong beri tahu saya.

Marnix
sumber
Masalahnya bukan hanya bukti dalam logika predikat atas model yang terbatas (dan mungil!), Atau saya akan menjawab daripada memasang hadiah. Tujuannya bukan untuk menyelesaikan masalah - tujuannya adalah untuk secara otomatis membuat masalah, dan dengan cara yang menarik.
@ Jo. Masalahnya, bahkan untuk satu set kecil, masih akan menjadi masalah 3SAT. Jika Anda hanya membuat AND dan OR, ini dapat menyebabkan hal-hal yang tidak memuaskan, jadi saya pikir akan sangat sulit untuk hanya menghasilkan puzzle acak. Teka-teki harus mengandung setidaknya beberapa batasan. Kadang-kadang, penalaran mundur bisa menjadi jawabannya (punya solusi, tinggalkan semuanya)
Marnix
Logika predikat umum sebenarnya lebih sulit daripada 3SAT; Namun, algoritma pembuktian modern benar-benar bagus dalam praktiknya. Selain itu, hanya membuat model, teka-teki, dan memeriksa solusi dapat dilakukan dalam waktu linier - triknya adalah memastikan kendala yang diberikan menghasilkan solusi yang unik dan dapat ditemukan.
@Jo, jadi adakah kendala yang bisa kita yakini untuk membuat puzzle ini? Pertanyaannya adalah: struktur data apa yang akan digunakan. Jadi saya masih berpikir bahwa Rulekelas adalah ide yang bagus. Pemodelan kendala ini masih dilakukan oleh predikat logika saya rasa.
Marnix
0

Saya tidak punya jawaban yang baik, tetapi mencari petunjuk tentang masalah yang sama, saya menemukan repositori ini di github:

https://github.com/nateinaction/Zebra-Puzzle

Ini berisi beberapa logika untuk memilih petunjuk dan memutuskan berapa banyak petunjuk yang Anda perlukan untuk membuat teka-teki yang dapat dipecahkan.

Vegan
sumber
-1

Ada ini untuk menyelesaikannya.

Tentu saja, saya pikir tidak akan terlalu sulit untuk bekerja mundur; yang memiliki daftar seperti ini:

  • Fred Red Dog

  • Steve Blue Cat

  • Bill Purple Whale

  • Eric Cyan Dolphin

Yang bisa dibuat dengan mudah, dan kemudian membuat seperangkat aturan dari itu.

Adapun penyimpanan, mengapa tidak satu set setiap hal yang terpisah, jadi [Fred, Steve, Bill, Eric] dan satu set jawaban [Fred, Red, Dog]. Kemudian miliki 'NAMA tidak (tidak) TINDAKAN OBYEK'.

Ketika Anda membahasnya, apakah solusi unik benar-benar penting? Selama game Anda dapat membaginya menjadi daftar, dan centang 'set 1 tidak mengandung Paus'.

Bebek Komunis
sumber
2
Caranya adalah, Anda ingin masalahnya tetap sulit. Jika aturan yang Anda hasilkan mengakui 90% dari kemungkinan kombinasi sebagai jawaban yang valid, itu bukan lagi teka-teki yang menarik.
Saya kira itu adalah poin yang valid - tetapi bukankah solusinya hanya dengan menurunkan jumlah petunjuk yang diberikan?
Bebek Komunis
1
Tidak. Spesifikasi yang kurang cenderung mengarah pada banyak kesimpulan yang valid. Spesifikasi yang berlebih cenderung mengarah pada satu kesimpulan yang sangat jelas. Teka-teki logika yang baik menghindari keduanya.
Ah ya, entah bagaimana saya melewatkannya. Saya akan mencoba dan menambahkan solusi yang lebih baik jika saya bisa memikirkan satu.
Bebek Komunis
Joe: Tepat sekali dengan komentar pertama Anda. Teka-teki yang memungkinkan Anda menyatukan petunjuk bersama-sama tidak seperti puzzle sebagai proyek seni taman kanak-kanak.
taserian