Tic-Tac-Toe
An important step towards the strong AI is the ability of an artificial agent to solve a well-defined problem. A project by the name 'tic-tac-toe' was one of such test problems. It's still up...
nc tic-tac-toe.2016.volgactf.ru 45679
ncコマンドで接続すると、次のとおり三目並べが始まります。2000試合やる必要がありますので、プログラムを書いて自動で対戦させます。
Welcome to Noughts & Crosses World Championship!
Please, name yourself.
aaa
The match is played over 2000 rounds, the winner of each round gets 1.0 points, the looser gets 0.0 points, and in case of a draw each player gets 0.5 points.
To make your move choose the empty cell and send it's index followed by '\n', e.g. '4\n'.The indices map:
0 | 1 | 2
---+---+---
3 | 4 | 5
---+---+---
6 | 7 | 8
Round number 1.
Server vs. aaa. Current score: 0.0 - 0.0
| |
---+---+---
| X |
---+---+---
| |
CPUはそれほど強くありませんので、次の優先順位で置く場所を決めていきます。
- 次にCPUに置かれるとこちらが負けてしまう場所
- 空いている場所の中で価値の高い順番(真ん中→四隅→各辺の中央)
この程度のアルゴリズムで十分勝ち越すことができます。このRubyプログラムを以下に記載します。
require "socket"
def seikei(ary)
return ary.collect do |item|
if item.strip == "" then 0
elsif item.strip == "O" then 1
elsif item.strip == "X" then -1
end
end
end
def check_winner(ary, who, pos)
tmp = ary.dup
if who != 0 then
tmp[pos] = who
end
for i in 0..2 do
#横方向
if tmp[i*3+0]+tmp[i*3+1]+tmp[i*3+2]==3 then
return 1
elsif tmp[i*3+0]+tmp[i*3+1]+tmp[i*3+2]==-3 then
return -1
end
#縦方向
if tmp[0+i]+tmp[3+i]+tmp[6+i]==3 then
return 1
elsif tmp[0+i]+tmp[3+i]+tmp[6+i]==-3 then
return -1
end
end
#斜め
if tmp[0]+tmp[4]+tmp[8]==3 then
return 1
elsif tmp[0]+tmp[4]+tmp[8]==-3 then
return -1
end
if tmp[2]+tmp[4]+tmp[6]==3 then
return 1
elsif tmp[2]+tmp[4]+tmp[6]==-3 then
return -1
end
return 0
end
def tictactoe(sock, ary)
cell = [4, 0, 2, 6, 8, 1, 3, 5, 7]
if ary.length != 9 then
return
end
tmp = seikei(ary)
if check_winner(tmp, 0, 0) != 0 then
ary.clear
return
end
sengo = tmp.inject {|sum, n| sum + n }
#X(-1)の方が多い場合はCPUがX(-1)
if sengo == -1 then cpu = -1
else cpu = 1
end
#次に置かれると負けてしまう場所に打つ
for i in 0..8 do
if tmp[i] == 0 then
if check_winner(tmp, cpu, i) == cpu then
printf(i.to_s + "\n")
sock.write(i.to_s + "\n")
STDOUT.flush
ary.clear
return
end
end
end
#価値の高い場所に打つ
cell.each do |i|
if tmp[i] == 0 then
printf(i.to_s + "\n")
sock.write(i.to_s + "\n")
STDOUT.flush
ary.clear
return
end
end
ary.clear
end
begin
sock = TCPSocket.open("95.213.237.91", 45679)
rescue
puts "TCPSocket.open failed : #$!\n"
else
ary = []
while sock.gets
buf = $_
printf( buf )
STDOUT.flush
if buf.start_with?("Please, name yourself.") then
printf("aaa\n")
sock.write("aaa\n")
STDOUT.flush
elsif buf.start_with?(" |") then
ary.concat(buf.chomp.split("|"))
tictactoe(sock, ary)
elsif buf.start_with?(" X |") then
ary.concat(buf.chomp.split("|"))
tictactoe(sock, ary)
elsif buf.start_with?(" O |") then
ary.concat(buf.chomp.split("|"))
tictactoe(sock, ary)
else
end
end
sock.close
end
以下が実行結果です。
Welcome to Noughts & Crosses World Championship!
Please, name yourself.
aaa
The match is played over 2000 rounds, the winner of each round gets 1.0 points, the looser gets 0.0 points, and in case of a draw each player gets 0.5 points.
To make your move choose the empty cell and send it's index followed by '\n', e.g. '4\n'.The indices map:
0 | 1 | 2
---+---+---
3 | 4 | 5
---+---+---
6 | 7 | 8Round number 1.
Server vs. aaa. Current score: 0.0 - 0.0
| |
---+---+---
| X |
---+---+---
| |
0
O | | X
---+---+---
| X |
---+---+---
| |
6
O | | X
---+---+---
| X |
---+---+---
O | | X
5
O | X | X
---+---+---
| X | O
---+---+---
O | | X
7
O | X | X
---+---+---
X | X | O
---+---+---
O | O | X
Round number 2.
Server vs. aaa. Current score: 0.5 - 0.5(略)
Round number 2000.
Server vs. aaa. Current score: 565.5 - 1433.5
| |
---+---+---
| |
---+---+---
| |
4
| |
---+---+---
| X |
---+---+---
| | O
0
X | | O
---+---+---
| X |
---+---+---
| | O
5
X | | O
---+---+---
O | X | X
---+---+---
| | O
6
X | O | O
---+---+---
O | X | X
---+---+---
X | | O
7
Server vs. aaa. Final score: 566.0 - 1434.0
Congratulations! Your flag is: VolgaCTF{tic_t@c_t0e_is_the_e@rly_step_t0wards_AI}
2000試合対戦して勝ち越しましたので、フラグが表示されました。2000試合は多すぎると思います。
フラグは、
VolgaCTF{tic_t@c_t0e_is_the_e@rly_step_t0wards_AI}
です。
