エントリー
この記事では、10x10のサイズのフィールドで三目並べゲームを作成しようとします。このゲームは、ブラウザーを介してプレイできるボット（コンピューター）を持つプレイヤー（人）です。 、次の3つの結果のいずれかの場合、ゲームは完了したと見なされます。
1）プレイヤーが勝った
2）コンピューターが勝った
3）描く
パッケージのインストール、検証、構成が意図的に見逃された、Erlangのインストールが繰り返し書かれた、さらに、このプログラムはOTPの原則に基づいて構築されたものではありません。 すべての重要なポイントに回路図の写真を添付します。
すべてのテストは鉄で実施されました。
RAM 4 GB、i5、MAC OS X
ゲームはブラウザで正常に動作します（残りはチェックされませんでした）：
Chrome 19.0.1084.56
FF 13.0.1
Safari 5.1.6（7534.56.5）
Opera 11.64
小さな辞書：
リスト-配列と見なすことができます。
シンボル-十字架またはつま先;
セル、ポイントは移動のためのセルであり、座標（X; Y）を持ちます。ここで、0 <XおよびY <= 10;
方向-4つのバリエーションのいずれか：水平、垂直、最初の対角線または2番目の対角線。
シーケンス-5つの座標のリスト。
ネットワーク接続
ユーザーと対話するために、プログラムはポート-8000をリッスンし、クライアントが接続した後、ゲームを初期化して接続を待ちます。
重要な点は、ユーザー側（ブラウザー）がキープアライブ（永続的）接続をサポートする必要があることです。事実、プレーヤーとプログラムとのすべての対話はajax getリクエストを使用して実装されます。この実装では、後続のすべてのajax getリクエストは1つの接続（ソケット）無制限の数量*
*ブラウザーが強制的に接続を切断する特定の番号は見つかりませんでしたが、1つの接続で最大1000個のajaxがリクエストを取得し、ブラウザーがソケットを閉じることを開始せず、最悪の場合、サーバーごとに50のゲームリクエストが必要になると明確に言うことができます。
クライアントの処理を担当するコードのスニペット：
s(Port)-> spawn( fun () -> {ok, Socket} = gen_tcp:listen(Port, [list,{active, false},{packet, http}]), accept_loop(Socket) end). accept_loop(Socket) -> {ok, CSocket} = gen_tcp:accept(Socket), Pid = spawn( fun () -> client_socket() end), gen_tcp:controlling_process(CSocket, Pid), Pid ! {take_socket, Csocket}, % race condition accept_loop(Socket). client_socket() -> Socket = receive {take_socket, S} -> S end, client_loop(Socket, [], []).
アルゴリズム
アルゴリズムの主なアイデアは評価関数に基づいており、すべての空のセルがスキャンされ、特定のセルの効率係数が計算されます。これは、特定のセルに移動した場合に得られるメリット、対戦相手に同様のアクション、特定のセルに移動した場合に得られるメリットです。
基本式：
G = M + A * N
M-このセルでのボットの利点
N-特定のセルでのプレイヤーの利益
A-攻撃性係数。係数が増加するとボットは防御戦略に入り、減少するとボットはイニシアチブを奪取しようとします。
ここで、さらに詳しく検討してください。
典型的なゲームの状況を想像してください：
最初に、1つのセルの近くのすべての座標を生成する必要があります。
3-セルが角型の場合
5-セルが初期または最終の場合
8-他のすべてのオプション付き
生成を担当するコード：
get_all_empty_points([]) -> []; get_all_empty_points([Head | Tail]) -> lists:usort(get_nearby_points(Head) ++ get_all_empty_points(Tail)). % get_nearby_points({X,Y}) when X =:= 1 andalso Y =:=1 -> [{X, Y+1}, {X+1, Y+1}, {X+1, Y}]; get_nearby_points({X,Y}) when X =:= 1 andalso Y =:=10 -> [{X+1, Y}, {X+1, Y-1}, {X, Y-1}]; get_nearby_points({X,Y}) when X =:= 10 andalso Y =:=10 -> [{X-1, Y}, {X-1, Y-1}, {X, Y-1}]; get_nearby_points({X,Y}) when X =:= 10 andalso Y =:=1 -> [{X, Y+1}, {X-1, Y+1}, {X-1, Y}]; % X,Y get_nearby_points({X,Y}) when X =:= 1 -> [{X, Y-1}, {X+1, Y-1}, {X+1, Y}, {X+1, Y+1}, {X, Y+1}]; get_nearby_points({X,Y}) when Y =:= 10 -> [{X+1, Y}, {X+1, Y-1}, {X, Y-1}, {X-1, Y-1}, {X-1, Y}]; get_nearby_points({X,Y}) when X =:= 10 -> [{X, Y-1}, {X-1, Y-1}, {X-1, Y}, {X-1, Y+1}, {X, Y+1}]; get_nearby_points({X,Y}) when Y =:= 1 -> [{X-1, Y}, {X-1, Y+1}, {X, Y+1}, {X+1, Y+1}, {X+1, Y}]; % get_nearby_points({X,Y}) -> [{X-1, Y+1}, {X, Y+1}, {X+1, Y+1}, {X+1,Y}, {X+1, Y-1}, {X, Y-1}, {X-1, Y-1}, {X-1, Y}].
移動が行われた各セルに対して同様のアクションを実行します。プレーヤーまたはボットの移動であるかどうかは関係ありません。その後、重複および既存の移動を削除します。 その結果、近くのすべてのセルの座標を含むリストを取得します。ドットは取得する座標を示します。
次に、各セルへの移動のメリットを直接計算する必要があります。 1つのセルのプライベートオプションを検討し、以前に受け取ったリスト内のすべてのセルに適用します。
現在のセルのすべての拡張子（ウェルまたはエンド）を生成する必要があります：水平、垂直、最初の対角線、2番目の対角線、図のドットで示されている-取得する結果
座標の生成を担当するコード：
generate_point (horizontal, {X, Y}) -> [{X2,Y} || X2<-lists:seq(X-4, X+4, 1), X2 > 0, X2 < 11]; generate_point (vertical, {X, Y}) -> [{X,Y2} || Y2<-lists:seq(Y-4, Y+4, 1), Y2 > 0, Y2 < 11]; generate_point (fdiagonal, {X, Y}) -> [{X2,Y2} || X2<-lists:seq(X-4, X+4, 1), Y2<-lists:seq(Y-4,Y+4, 1), X2 > 0, Y2 > 0, X2 < 11, Y2 < 11, X2-Y2 == XY]; generate_point (sdiagonal, {X, Y}) -> [{X2,Y2} || X2<-lists:seq(X-4, X+4, 1), Y2<-lists:seq(Y-4,Y+4, 1), X2 > 0, Y2 > 0, X2 < 11, Y2 < 11, X2+Y2 == X+Y].
ここで、水平方向の有効性を評価する特定のバリアントを検討します。これらのアクションは、他の方向（垂直、斜め）でもまったく同じです。
5セルの長さのすべてのセグメントを調べる必要があります。これは、最も極端なポイントを見つけて5セルをカウントし、1セルのシフトでさらに4セグメントを見ると、視覚的に画像を見ることができます。
上の図では、簡単な例がゲームの状況に関係なく、説明のみを目的として示されています。 5つのセルのセクションを見るとき、5つのシーケンスのそれぞれについていくつかの指示に従う必要があります。
1）シーケンスが反対のシンボルによって中断された場合、このシーケンスの重みはゼロに等しくなります。
2）現在のシンボルを持つセルがシーケンス内で見つかった場合、カウンター値は1増加し、次の位置に移動します。
3）シーケンスに空のセルがある場合、カウンター値を増加させずに、それをスキップして次の位置に移動します。
4）5つの現在のシンボルのシーケンスがアセンブルされ、シーケンスがボットによって収集された場合、シーケンスの重量は10,000に等しく、シーケンスがプレイヤーによってアセンブルされた場合、シーケンスの重量は1,000に等しく、ボットは勝利をより高く評価する必要があるという事実この状況で彼らの防衛より。
5）シーケンスの長さが1の場合、それを0に等しくします。これは、想像上の動きにすぎません。
評価関数式：
L
Gh = ∑ K C
i = 1
Lは、非ゼロシーケンスの総数です。
K-係数、この場合-3
Cは、シーケンス、段落2の文字の総数です。
同様に、すべての方向について計算します：垂直、2つの対角線について、すべての値を要約します。これは、等価な数値の利点です。
M、N = Ghor + Gver + Gfdiag + Gsdiag
パフォーマンスの計算を担当するコード：
calculate_point_gravity(_, _, [], _) -> []; calculate_point_gravity(MovesX , MovesY, [Move | Rest], Aggress) -> PGravityX = calculate(generate_point(horizontal, Move), MovesX ++ [Move], MovesY, [], Move, 1000) + calculate(generate_point(vertical, Move), MovesX ++ [Move], MovesY, [], Move, 1000) + calculate(generate_point(fdiagonal, Move), MovesX ++ [Move], MovesY, [], Move, 1000) + calculate(generate_point(sdiagonal, Move), MovesX ++ [Move], MovesY, [], Move, 1000), PGravityY = calculate(generate_point(horizontal, Move), MovesY ++ [Move], MovesX, [], Move, 10000) + calculate(generate_point(vertical, Move), MovesY ++ [Move], MovesX, [], Move, 10000) + calculate(generate_point(fdiagonal, Move), MovesY ++ [Move], MovesX, [], Move, 10000) + calculate(generate_point(sdiagonal, Move), MovesY ++ [Move], MovesX, [], Move, 10000), PGravity = PGravityY + Aggress * PGravityX, [{PGravity, Move}] ++ calculate_point_gravity(MovesX, MovesY, Rest, Aggress). loop(_,_,_,0, Counter) -> Counter; loop([],_,_,_, Counter) -> Counter; loop(_,_,_,_, opponent_point_find) -> 0; loop([FC | RC], MovesX, MovesY, Num, Counter) -> Res = case exist_in_list(MovesX, FC) of true -> Counter + 1; % false -> % case exist_in_list(MovesY, FC) of true -> opponent_point_find; % false -> Counter % , end end, loop(RC ,MovesX, MovesY, Num - 1, Res). calculate(CList, MovesX, MovesY, Current, BreakElement, W) when Current == BreakElement -> 0; calculate(CList, MovesX, MovesY, Current, BreakElement, W) -> Res = loop(CList, MovesX, MovesY, 5, 0) NewRes = case Res of opponent_point_find -> 0; 0 -> 0; 1 -> 0; % 1 5 -> W; % 5, _ -> math:pow(3, Res) % end, [Head | Rest] = CList, NewRes + calculate(Rest, MovesX, MovesY, Head, BreakElement, W).
関数calculateとcalculate_point_gravityでは、末尾再帰は使用されず、反復回数が無視できるため、これがパフォーマンスやメモリ消費に何らかの影響を与えるとは思わないことに注意してください。
各セルの効率係数を計算したら、最大のものを選択します。
lists:max(calculate_point_gravity(PlayerMovesX , PlayerMovesY, AllVariants, Agress)).
ランダム性を追加することもできますが、これは不要であることがわかりました。
確認する
ゲームは、勝者と敗者という2つの側面を定義せずに意味を失いますが、引き分けのオプションもあります。
勝利チェックアルゴリズムを簡単に確認しましょう。チェックは後続の各プレーヤーのターン後に初期化され、ターンの順に3つの結果をチェックします。プレーヤーが移動します。
基本的なアルゴリズムは図に示されています（すべての方向に8本の光線があり、圧縮のために見えません）-現在のシンボルですべてのセルを表示し、カウンター値を増やしますが、わずかなニュアンスで、4方向のそれぞれが2つの部分に分割されます：両方の部分をチェックした後、合計して1つを追加します。合計が5の場合、勝ちのシーケンスが見つかります。
残り
そしてもちろん、デモ：
http://88.198.65.2:8000/
ゲームの複雑さは動的であり、デフォルトでは次の動きまで変更できます-デフォルトでは0.8、難易度は大きくなります-ボットは防御戦略に入り、攻撃戦略は少なくなります、複雑さを試すことをお勧めします、私の意見では、ボットは[0.5 、1]。
プロキシの背後にいる人々、またはポート8000が閉じられている人々に事前に謝罪しますが、ゲームをポート80に転送する方法はありません。
github'eで入手可能なソース-github.com/Tremax/eTicTacToe
私はクライアントの部分を考慮しません、すべてがそこに些細であるという事実のために。
参照資料
algolist.manual.ru/games/fiveinarow.php
ご意見をお聞かせください。