Strategi dalang

19

Saya hanya bisa menemukan tantangan kode-golf untuk Mastermind, jadi inilah versi tantangan kode yang ingin saya ambil sendiri.

Strategi optimal untuk game Mastermind normal, MM (4,6), ditemukan oleh Koyama dan Lai pada tahun 1993, memiliki rata-rata # tebakan = 5625/1296 ~ 4.34. MM (5,8) masih belum terpecahkan, tetapi diperkirakan memiliki rata-rata tebakan ~ 5.5.

Tugas Anda adalah membuat strategi MM (5,8), yaitu untuk 5 lubang dan 8 warna, yang mencakup semua pow(8,5) = 32768solusi berbeda yang mungkin. Jelas, itu tidak harus yang optimal. Anda memiliki dua pilihan:

  1. Poskan program deterministik yang menghasilkan strategi. Program harus dapat dikompilasi / dijalankan pada Windows 7, Mac OS X atau Linux tanpa perangkat lunak tidak bebas tambahan.
  2. Publikasikan strategi Anda (bersama dengan nama StackExchange Anda) di suatu tempat di Internet dan posting URL di sini.

Dalam kedua kasus, nyatakan skor (lihat di bawah) di tajuk jawaban.

Strategi harus dikodekan sesuai dengan tata bahasa berikut:

strategy : guessing-strategy | known-solution-strategy
guessing-strategy : '{' guess ':' branches '}'
known-solution-strategy : guess
guess : color color color color color
color : 'A'..'H'
branches : '{' branch (',' branch)* '}'
branch : reply ':' strategy
reply : number-of-blacks number-of-whites
number-of-blacks : number-of-key-pegs
number-of-whites : number-of-key-pegs
number-of-key-pegs : '0'..'5'

Algoritma yang digunakan untuk menentukan jumlah pasak kunci hitam / putih dijelaskan di http://en.wikipedia.org/wiki/Mastermind_(board_game)

Perhatikan bahwa balasan "50" (yaitu tebakan yang benar) tersirat dan bukan bagian dari tata bahasa.

Penilaian: N = jumlah jumlah tebakan untuk masing-masing 32768 jalur / solusi. Strategi dengan N terendah menang. Tie-break pertama: Jumlah tebakan maksimum terendah. Ikatan kedua: Jawaban pertama yang diposting. Kompetisi berakhir 1 Agustus 2014 0:00 GMT .


Contoh strategi untuk MM (2,3) dengan skor = 21:

{AB:{10:{AC:{10:AA,01:CB,00:BB}},02:BA,01:{BC:{01:CA}},00:CC}}

Dengan menggunakan strategi ini, 9 kemungkinan game akan berjalan seperti ini:

  • AB 20
  • AB 10, AC 20
  • AB 10, AC 10, AA 20
  • AB 10, AC 01, CB 20
  • AB 10, AC 00, BB 20
  • AB 02, BA 20
  • AB 01, BC 20
  • AB 01, BC 01, CA 20
  • AB 00, CC 20

Saya akan segera memposting verifikasi strategi MM berbasis Java (5,8) untuk kenyamanan Anda.

MrBackend
sumber
Saya mengalami kesulitan memahami bagaimana contoh strategi MM (2,3) diterapkan. Bisakah Anda memposting game contoh yang menjelaskan strateginya?
@tolos saya menambahkan semua 9 :)
MrBackend
Akan lebih bagus jika verifier Anda bisa menghasilkan skor juga!
Bukan Charles
@ Charles Akan melakukannya!
MrBackend
2
Apakah Anda bersedia mengubah tata bahasa Anda untuk memungkinkan respons yang sama untuk beberapa kombinasi pasak kunci? Suka {AB:{10|01:BB}}? Saya memang punya jawaban, tapi itu cukup naif dan karena struktur pohon tata bahasa itu tidak skala sama sekali (4 lubang, 3 warna, menghasilkan strategi 147MB, yang saya dapat mengurangi secara signifikan dengan menggabungkan bagian-bagian dari pohon).
Martin Ender

Jawaban:

6

Jawa

Algoritma saya untuk skor MM (5,8) dengan 177902 178006 182798 182697 dengan kedalaman maksimum 8 9 dan hanya perlu beberapa detik (pada komputer saya yang lambat).

Contoh output dari strategi untuk MM (2,3) dengan skor = 21 ditemukan oleh algoritma ini terlihat seperti ini:

{BC:{00:AA,01:AB:{01:CA},02:CB,10:AC:{00:BB,01:BA,10:CC}}}

Tidak ada yang menarik dengan algoritma saya. Tidak ada penemuan. Saya hanya mengikuti resep yang ditemukan di internet dan mengompresnya ke dalam kode Java ini. Satu-satunya optimasi yang saya lakukan adalah mencoba mengoptimalkan baris kode (dengan cara tertentu). Bunyinya seperti ini:

  1. Buat himpunan awal S0 dari semua kode yang mungkin menjadi himpunan S. saat ini
  2. Codebreaker menemukan tebakan (serakah) yang bagus untuk S. Setiap tebakan mengarah ke partisi P dari S, di mana setiap subset S 'mengumpulkan semua kode (dari S) yang memiliki jawaban yang sama pada tebakan itu. Tebakan yang baik memiliki partisi yang baik, sebagai partisi yang memberikan informasi paling banyak untuk tebakan itu.
  3. Ambil tebakan yang baik dan P-nya. Untuk setiap nonempty S 'di P terapkan codebreaker rekursif (langkah 2).

@ MrBackend: Menulis verifier itu sulit, kurasa. ;-)

import java.util.TreeMap;
import java.util.Vector;

public class MM {
    Vector<String> codeset = new Vector<String>();
    String guess;
    TreeMap<Integer, MM> strategy = new TreeMap<Integer, MM>();

    public String toString() {
        String list="";
        for (Integer reply: strategy.keySet()) {
            if (strategy.get(reply)!=null) list+=(list.length()>0?",":"")+(reply<10?"0":"")+reply+":"+strategy.get(reply);
        }
        if (list.length()>0) return guess+":{"+list+"}"; else return guess;
    }

    MM() { }

    MM(int h, int c) {
        for (int i = 0; i < Math.pow(c, h); i++) {
            String code = "";
            for (int j = 0, p=i; j < h; j++) {
                code+="ABCDEFGH".charAt(p%c);
                p/=c;
            }
            codeset.add(code);
        }
    }

    int replyAccordingToDonaldKnuth(String secret, String guess) {
        int black=0;
        int totalHitsBlackAndWhite=0;
        for (char n = 'A'; n <= 'H'; n++) {
            int a=0, b=0;
            for (int i = 0; i < secret.length(); i++) {
                if (secret.charAt(i)==n) a++;
                if ( guess.charAt(i)==n) b++;
            }
            totalHitsBlackAndWhite+=Math.min(a, b);
        }
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) black++;
        }
        return 10 * black + (totalHitsBlackAndWhite-black);
    }

    int reply(String secret, String guess) {
        return replyAccordingToDonaldKnuth(secret, guess);
    }

    MM codebreaker(Vector<String> permuts) {
        int fitness=0;
        MM protostrategy=null;
        for (int greedy = 0; greedy < Math.min(permuts.size(), 200); greedy++) {
            MM tmp=partition(permuts, permuts.get(greedy));
            int value=tmp.strategy.size();
            if (fitness<=value) {
                fitness=value;
                protostrategy=tmp;
                protostrategy.guess=permuts.get(greedy);
            }
        }
        if (protostrategy!=null) {
            for (Integer reply: protostrategy.strategy.keySet()) {
                protostrategy.strategy.put(reply, codebreaker(protostrategy.strategy.get(reply).codeset));
            }
        }
        return protostrategy;
    }

    MM partition(Vector<String> permuts, String code) {
        MM protostrategy=new MM();
        for (int c = 0; c < permuts.size(); c++) {
            int reply=reply(permuts.get(c), code);
            if (!protostrategy.strategy.containsKey(reply)) protostrategy.strategy.put(reply, new MM());
            if (permuts.get(c)!=code) protostrategy.strategy.get(reply).codeset.add(permuts.get(c));
        }
        return protostrategy;
    }

    public static void main(String[] args) {
        MM mm = new MM(5,8);
        System.out.println("{"+mm.codebreaker(mm.codeset)+"}");
    }
}

Beberapa komentar:

  1. Tidak diperlukan pemeriksaan konsistensi karena set S dan partisinya dibangun dengan cara (otomatis) yang konsisten.
  2. Memilih tebakan yang baik dari S0 (bukan S) masuk akal. Tetapi saya tidak mengikuti pendekatan ini dalam kode saat ini.
  3. Pencarian serakah saya secara artifisial dipangkas menjadi 200 percobaan.
  4. Saya tahu, "memberikan sebagian besar informasi untuk dugaan" tidak terlalu tepat. Ide sederhananya adalah memilih partisi dengan jumlah subset terbanyak.
  5. Hasilnya sangat tergantung pada bagaimana Anda menghitung balasan (..). Akhirnya saya mengadaptasi ekspresi Donald Knuth.

Strategi untuk MM(5,8) dapat ditemukan di sini . GitHub memiliki beberapa masalah menampilkan garis yang panjang, jadi klik tombol Raw .

Bob Genom
sumber
hai cara cantik mencetak teks github sehingga hasilnya dapat diubah menjadi panduan pencarian .. dari titik awal pertama 'HHCAA' .. dan langkah selanjutnya tergantung pada balasan ... dan selanjutnya dan seterusnya. Format teks mentah saat ini tidak mudah untuk pemindaian manual .. teknik yang saya cari adalah bagaimana mengurai kurung bersarang dan mendapatkan tata letak tabel yang bagus yang lebih mudah diikuti sampai akhir, mirip dengan daftar berpoin dalam pertanyaan untuk MM (2,3). Terima kasih. Semoga Anda bisa mengerti apa yang saya cari. (lebih suka python untuk mengurai str)
ihightower
2

Rubi

EDIT: Menambahkan beberapa logika untuk mengecualikan tebakan yang tidak mungkin. Oleh karena itu, strategi sekarang mematuhi format yang diberikan dan jauh lebih mudah dikelola.

Jadi, inilah salah satu upaya untuk mewujudkannya. Ini cukup naif (dan tidak terlalu terbaca - membantu untuk membaca cabang if / elsif / else dari bawah ke atas).

Holes, Colors = ARGV.map &:to_i

ColorChars = ('A'..'H').to_a

def is_possible(guess, blacks, result)
    blacks == guess.chars.zip(result.chars).count {|chars| chars[0] == chars[1]}
end

def print_strategy(known_colors, remaining_permutations, next_color)
    char = ColorChars[next_color]
    if remaining_permutations
        guess = remaining_permutations[0]
        print guess
        if remaining_permutations.length > 1
            print ':{'
            (Holes-1).times do |i|
                new_permutations = (remaining_permutations - [guess]).select { |perm| is_possible(guess, i, perm) }
                next if new_permutations.empty?
                print "#{i}#{Holes-i}:"                
                print '{' if new_permutations.length > 1
                print_strategy(known_colors, new_permutations, next_color)
                print '}' if new_permutations.length > 1
                print ',' if i < Holes-2
            end
            print '}'
        end
    elsif known_colors.length == Holes
        print_strategy(known_colors, known_colors.chars.permutation.map(&:join).uniq, next_color)
    elsif next_color == Colors-1
        print_strategy(known_colors+char*(Holes - known_colors.length), remaining_permutations, next_color+1)
    else
        print char*Holes, ':{'

        (Holes - known_colors.length + 1).times do |i|
            break if i == Holes
            print "#{i}0:"
            print '{' if next_color < Colors-2 || i > 0 || known_colors.length > 0
            print_strategy(
                known_colors+char*i,
                remaining_permutations,
                next_color+1
            )
            print '}' if next_color < Colors-2 || i > 0 || known_colors.length > 0
            print ',' if i < (Holes - known_colors.length) && i < Holes-1
        end
        print '}'
    end
end

print '{'
print_strategy('', nil, 0)
puts '}'

Pertama, saya mencoba 5 dari masing-masing warna: AAAAA, BBBBB, dll Dari bahwa saya mencari tahu mana warna yang benar-benar digunakan dalam pola. Dan kemudian saya hanya mencoba semua permutasi dari warna yang diberikan, menghilangkan yang telah dikesampingkan oleh pasak hitam.

Inilah MM(2,3)strateginya:

{AA:{00:{BB:{00:CC,10:{BC:{02:CB}}}},10:{BB:{00:{AC:{02:CA}},10:{AB:{02:BA}}}}}}

Strategi untuk MM(5,8)mengambil 376KB dan dapat ditemukan di sini . GitHub memiliki beberapa masalah menampilkan garis yang panjang, jadi klik tombol Raw .

Sekarang jika saya mendapatkan verifikasi, saya juga bisa memberi tahu Anda berapa skor saya yang sebenarnya. :)

Martin Ender
sumber
Merasa tidak enak tentang verifikasi belum dipublikasikan, tetapi sedang dalam perjalanan ... Ada yang salah dengan strategi (pertama) MM (2,3) Anda, misalnya jika solusinya adalah AB: Guess = AA; balas = 10; tebak = BB; reply = 10, yang tidak ada strategi. Saya akan melihat saran Anda untuk mengelompokkan balasan, tetapi seharusnya tidak perlu untuk strategi yang baik, karena serangkaian solusi yang memungkinkan terpisah untuk balasan yang berbeda.
MrBackend
@ MrBackend Tangkapan yang bagus, saya melewatkan kotak di sana. Seharusnya sudah diperbaiki sekarang. Adapun tata bahasa, tentu saja itu tidak perlu untuk strategi yang baik , tetapi saya pikir Anda mungkin bersedia sedikit menurunkan bar. ;) Jika orang dapat mengirimkan entri yang lebih sederhana (seperti milik saya), Anda mungkin lebih beruntung mendapatkan kiriman menarik yang secara bertahap membaik, daripada harus memasukkan semua kombinatorik sejak awal.
Martin Ender
Inilah masalahnya: Saya akan menyelesaikan verifikasi saat ini dan menerbitkannya (sebagai aplikasi web - terlalu besar untuk disisipkan di sini). Sayangnya, itu mungkin terlalu ketat, karena menganggap tidak mungkin membalas kesalahan. Setelah itu, saya akan mengadaptasinya untuk mendukung beberapa balasan dan hanya memancarkan peringatan untuk balasan yang tidak mungkin. Karena itu, strategi 1.3G MM (4,4) Anda harus mengandung banyak balasan yang tidak mungkin dan / atau tebakan yang tidak mengurangi, karena ukuran perkiraan strategi MM yang layak (5,8) adalah segelintir MB.
MrBackend
@ MrBackend Tentu saja strategi saya mengandung banyak balasan yang tidak mungkin. Itulah yang saya maksud dengan "Saya tidak melakukan kombinatorik". ;) Jika terlalu merepotkan bagi Anda untuk mendukungnya dan mengelompokkan balasan, jangan khawatir, maka saya akan berupaya menghilangkan tebakan yang tidak mungkin.
Martin Ender
@ MrBackend Kabar baik, saya memperbaikinya. :) Saya harap strateginya valid sekarang. Beritahu saya jika masih ada masalah dengan itu.
Martin Ender