Tantangan ini adalah tentang permainan Tic Tac Toe, tetapi dimainkan dengan torus.

Cara bermain

Untuk membuat papan permainan yang diperlukan, Anda mulai dengan papan permainan Tic Tac Toe biasa. Pertama, lipat menjadi silinder dengan menyatukan sisi kiri dan kanan. Kemudian lipat menjadi torus dengan menyatukan ujung atas dan bawah. Berikut ini visualisasi sederhana papan permainan dengan beberapa gerakan yang dimainkan (Sick Paint skill!).

Aturan Tic Tac Toe pada torus adalah sama dengan Tic Tac Toe biasa. Setiap tempat pemain bergantian Xs dan Os. Yang pertama dengan 3 simbol yang sama berturut-turut, satu kolom atau satu dalam kemenangan diagonal.

Karena torus cukup sulit untuk divisualisasikan, kami hanya memproyeksikan papan kembali ke atas kertas. Sekarang kita bisa memainkan permainan sebagai Tic Tac Toe biasa. Satu-satunya perbedaan adalah, Anda juga bisa menang dengan 3 simbol yang sama dalam diagonal yang rusak. Misalnya Pemain 1 (X) memenangkan papan berikut. Anda dapat melihat ini dengan mudah dengan mengubah tampilan pada torus sedikit.

Jika tertarik, Anda dapat bermain Tic Tac Toe di Torus di Torus Games . Ada versi Windows, Mac, dan Android.

Game yang Optimal

Dalam tantangan ini tertarik pada game yang optimal. Game yang optimal adalah game, di mana kedua pemain memainkan strategi yang optimal. Pada papan permainan papan Tic Tac Toe reguler optimal selalu berakhir imbang. Menariknya di papan torus selalu pemain pertama yang menang. Bahkan permainan di papan torus tidak pernah bisa berakhir imbang (juga jika pemain bermain tidak optimal).

Strategi optimal sangat mudah:

• Jika Anda bisa menang dengan menempatkan simbol Anda, lakukanlah.
• Kalau tidak, jika lawan Anda memiliki dua simbol dalam satu baris / kolom / agonal, cobalah untuk memblokirnya. Kalau tidak, lakukan apa yang Anda inginkan.
• Kalau tidak, lakukan apa yang Anda inginkan.

Setiap permainan optimal terdiri dari 7 gerakan tepat dan gerakan ini dapat dijelaskan dengan cara berikut:

1. Pemain 1 menempatkan X di mana saja di papan tulis (9 pilihan)
2. Pemain 2 menempatkan O di mana saja di papan tulis (8 pilihan)
3. Pemain 1 menempatkan X di mana saja di papan tulis (7 pilihan)
4. Langkah Player 2 mungkin dipaksakan (1 pilihan), jika tidak, ia menempatkan O di mana saja (6 pilihan)
5. Langkah pemain 1 dipaksa (1 pilihan)
6. Player 2 terperangkap dalam garpu (Player 1 dapat menang dalam dua cara berbeda), jadi Player 2 harus memblokir Player 1 dalam satu cara (2 pilihan)
7. Pemain 1 menempatkan langkah terakhir dan menang (1 pilihan)

Ada 9 * 8 * 1 * 6 * 1 * 2 * 1 + 9 * 8 * 6 * 1 * 1 * 2 * 1 = 1728 game optimal berbeda di papan proyeksi kami. Di sini Anda dapat melihat satu permainan optimal yang khas:

Jika kita memberi label pada setiap sel papan dengan angka 0-8, kita dapat menggambarkan game ini dengan angka 3518207. X pertama adalah tempat di sel 3 (baris tengah, kolom kiri), daripada O di sel 5 (baris tengah, kolom kanan), daripada X di sel 1 (baris atas, kolom tengah), ...

Menggunakan notasi digit ini, kami secara otomatis membuat pesanan. Sekarang kita dapat mengurutkan semua game optimal 1728 dan kita mendapatkan daftar:

Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
   ...
Game 0674: 3518207
   ...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
   ...
Game 1726: 8765034
Game 1727: 8765043

Tantangan

Daftar ini adalah bagian dari pekerjaan Anda. Anda akan menerima satu nomor kantara 0 dan 1727 dan Anda harus mengembalikan kgame ke-4 dalam notasi digit dari daftar yang diurutkan.

Tulis fungsi atau program, yang menerima angka k(bilangan bulat) menghitung permainan koresponden. Anda dapat membaca input melalui STDIN, argumen baris perintah, prompt atau argumen fungsi dan mencetak hasilnya (7 digit) dalam format yang dapat dibaca (misalnya 0123845atau [0, 1, 2, 3, 8, 4, 5]) atau mengembalikannya menggunakan string (format yang dapat dibaca manusia) atau integer (berisi semua digit dalam basis 10), atau dalam format array / daftar apa pun.

Jenis tantangannya adalah kode-golf. Karenanya kode terpendek menang.

JavaScript (ES6), 266 308 317 334 341

Fungsi mengembalikan string. Sunting Ditemukan solusi aritmatika untuk fungsi M (akhirnya!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Sangat naif , bisa disingkat dengan banyak cara . Ini hanya menyebutkan semua nilai hukum yang mungkin dan mengembalikan apa yang ditemukan di tempat n. Fungsi M mengembalikan posisi di antara dua sel, yaitu gerakan wajib untuk memblokir pemain yang berlawanan.

Lebih mudah dibaca

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position

Oktaf, 467 369 363 309 297 karakter

297:

global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

Satu-satunya perubahan yang relevan adalah bahwa kami tidak pernah memeriksa apakah pemain saat ini dapat menang, hanya memeriksa kemungkinan lawan untuk memenangkan giliran berikutnya . Karena satu-satunya putaran yang dapat dimenangkan pemain 1 adalah turn 7 , ini adalah satu-satunya tempat ketika algoritma akan menghasilkan permainan yang tidak optimal, tetapi sangat mudah untuk menyaring situasi seperti itu. Kami cukup memverifikasi setiap game yang dihasilkan jika dimenangkan oleh pemain 1 - jika tidak, langkah pada gilirannya 7 tidak benar, jadi kami tidak menambahkan game ini ke tabel game yang optimal.

(Persisnya setengah permainan yang dihasilkan oleh aturan ini salah, yaitu pada putaran ke-7 pemain 1 selalu memiliki dua kemungkinan untuk memblokir pemain dua, tetapi hanya satu yang akan membuatnya menang secara instan).

Menggunakan:

$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

Kode ungolfed seperti:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;
 allgames=[];

 function r=canbewon(by)
  global t m
  q=[t==by;t==(3-by)]*m;
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));
 end

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));