Erlang पर टिक टीएसी को पैर की अंगुली

प्रविष्टि

लेख में हम 10x10 आकार के एक क्षेत्र पर टिक-टैक-टो का एक खेल लिखने की कोशिश करेंगे, एक खिलाड़ी (व्यक्ति) एक बॉट (कंप्यूटर) के साथ एक ब्राउज़र के माध्यम से खेलने की क्षमता के साथ खेल को 3 परिणामों में से एक के मामले में पूरा माना जाता है:

1) खिलाड़ी जीता
2) कंप्यूटर जीता
3) ड्रा

इस तरह के क्षण: स्थापना, सत्यापन, संकुल के विन्यास को जानबूझकर याद नहीं किया जाता है, एरलांग की स्थापना को बार-बार लिखा गया है, इसके अलावा, यह कार्यक्रम ओटीपी के सिद्धांतों पर नहीं बनाया गया है। मैं योजनाबद्ध चित्रों के साथ सभी महत्वपूर्ण बिंदुओं के साथ होगा।

सभी परीक्षण लोहे पर किए गए थे:

रैम 4 जीबी, आई 5, मैक ओएस एक्स

खेल ब्राउज़र में सही ढंग से काम करता है (बाकी की जाँच नहीं की गई थी):
क्रोम 19.0.1084.56
एफएफ 13.0.1
सफारी 5.1.6 (7534.56.5)
ओपेरा 11.64

एक छोटा शब्दकोष:

सूची - एक सरणी के रूप में माना जा सकता है;
प्रतीक - एक क्रॉस या एक पैर की अंगुली;
एक सेल, एक बिंदु एक चाल के लिए एक सेल है, जिसमें निर्देशांक (एक्स; वाई) है, जहां 0 <एक्स और वाई <= 10;
दिशा - 4 भिन्नताओं में से कोई भी: क्षैतिज, ऊर्ध्वाधर, पहला विकर्ण या दूसरा विकर्ण;
अनुक्रम - 5 निर्देशांक की एक सूची।

नेटवर्क कनेक्टिविटी

उपयोगकर्ता के साथ बातचीत करने के लिए, प्रोग्राम पोर्ट - 8000 को सुनेगा, और कनेक्शन के लिए प्रतीक्षा करेगा, क्लाइंट कनेक्ट होने के बाद, गेम को इनिशियलाइज़ करेगा।

एक महत्वपूर्ण बिंदु यह है कि उपयोगकर्ता पक्ष (ब्राउज़र) को जीवित-स्थायी (स्थायी) कनेक्शन का समर्थन करना चाहिए, तथ्य यह है कि कार्यक्रम के साथ खिलाड़ी के सभी इंटरैक्शन को अजाक्स प्राप्त अनुरोधों के माध्यम से कार्यान्वित किया जाता है, इस कार्यान्वयन के बाद सभी अजाक्स के अनुरोध एक कनेक्शन (सॉकेट) के माध्यम से प्राप्त होंगे। असीमित मात्रा में *।

* मुझे एक विशिष्ट संख्या नहीं मिली, जिसके बाद ब्राउज़र कनेक्शन को जबरदस्ती डिस्कनेक्ट कर देते हैं, लेकिन मैं असमान रूप से कह सकता हूं कि 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, [], []). 

एल्गोरिथ्म

एल्गोरिथ्म का मुख्य विचार एक मूल्यांकन कार्य पर आधारित है, सभी खाली कोशिकाओं को स्कैन किया जाता है और किसी दिए गए सेल के लिए दक्षता गुणांक की गणना की जाती है, यह लाभ है कि अगर हम किसी दिए गए सेल में कदम रखते हैं, तो एक प्रतिद्वंद्वी के लिए इसी तरह के कार्यों, किसी दिए गए सेल में कदम रखने से उसे क्या लाभ होगा। ।

आधार सूत्र:

जी = एम + ए * एन

एम - इस सेल में बॉट का लाभ
एन - किसी दिए गए सेल में खिलाड़ी का लाभ
ए - आक्रामकता गुणांक, यदि गुणांक में वृद्धि हुई है, तो बॉट रक्षात्मक रणनीति में जाएगी, अगर कम हो जाती है, तो बॉट पहल को जब्त करने की तलाश करेगा।

अब अधिक विस्तार से विचार करें:

एक विशिष्ट खेल की स्थिति की कल्पना करें:



पहले आपको एक सेल के लिए सभी पास के निर्देशांक उत्पन्न करने की आवश्यकता है, वे क्रमशः हो सकते हैं:

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}]. 

हम प्रत्येक सेल के लिए समान कार्य करते हैं जिसमें यह कदम उठाया गया था, इससे कोई फर्क नहीं पड़ता कि यह खिलाड़ी या बॉट की चाल है, जिसके बाद हम डुप्लिकेट हटाते हैं और पहले से ही मौजूदा चाल। नतीजतन, हमें पास की सभी कोशिकाओं के निर्देशांक के साथ एक सूची मिलती है, डॉट्स उन निर्देशांक को दर्शाते हैं जो हमें प्राप्त करने चाहिए:



इसके बाद, आपको प्रत्येक सेल में ले जाने के लाभ की सीधे गणना करने की आवश्यकता है। एक सेल के लिए एक निजी विकल्प पर विचार करें और उस सूची में सभी कोशिकाओं पर लागू करें जो हमें पहले प्राप्त हुई थी।

हमें वर्तमान सेल के सभी एक्सटेंशन (अच्छी तरह से, या अंत, जो भी हो) उत्पन्न करने की आवश्यकता है: क्षैतिज, ऊर्ध्वाधर, पहला विकर्ण, दूसरा विकर्ण, आंकड़े में डॉट्स द्वारा इंगित किया गया - परिणाम हमें मिलना चाहिए:



निर्देशांक बनाने के लिए जिम्मेदार कोड:

 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 कोशिकाओं की गणना करते हैं, और फिर एक कक्ष में एक बदलाव के साथ हम 4 और खंडों को देखते हैं, आप नेत्रहीन चित्र देख सकते हैं:



उपरोक्त तस्वीर में, केवल उदाहरण के लिए उदाहरण के लिए दिखाया गया है, खेल की स्थिति से संबंधित नहीं। जब हम 5 कोशिकाओं के एक खंड को देखते हैं, तो हमें प्रत्येक 5 क्रमों के लिए कुछ निर्देशों का पालन करना चाहिए:

1) यदि अनुक्रम विपरीत प्रतीक द्वारा बाधित है, तो इस अनुक्रम का वजन शून्य के बराबर है।
2) यदि वर्तमान चिन्ह वाला सेल अनुक्रम में पाया जाता है, तो काउंटर मान 1 से बढ़ जाता है, और अगली स्थिति में चला जाता है।
3) यदि अनुक्रम में एक खाली सेल है, तो हम इसे छोड़ देते हैं और काउंटर वैल्यू नहीं बढ़ाते हुए अगली स्थिति में चले जाते हैं।
4) यदि 5 वर्तमान प्रतीकों का एक अनुक्रम इकट्ठा किया जाता है, तो अनुक्रम बहुत अधिक वजन के बराबर होता है, यदि अनुक्रम एक बॉट द्वारा एकत्र किया गया था - इसका वजन 10,000 के बराबर है, यदि अनुक्रम एक खिलाड़ी द्वारा इकट्ठा किया जाता है - इसका वजन 1,000 के बराबर है, तथ्य यह है कि बॉट को अपनी जीत का मूल्यांकन करना चाहिए इस स्थिति में उनकी रक्षा की तुलना में।
5) यदि अनुक्रम की लंबाई 1 है, तो इसे 0 के बराबर करें, यह केवल हमारी काल्पनिक चाल है।

मूल्यांकन समारोह सूत्र:

एल
घ = ∑ के ^सी
मैं = १

एल नॉनजेरो सीक्वेंस की कुल संख्या है
के - गुणांक, हमारे मामले में - 3
सी, अनुक्रम 2 में वर्णों की कुल संख्या है, पैराग्राफ 2।

इसी तरह, हम सभी दिशाओं के लिए गणना करते हैं: ऊर्ध्वाधर, 2 विकर्णों के लिए, फिर हम सभी मूल्यों को संक्षिप्त करते हैं, यह संख्यात्मक समकक्ष में लाभ है:

म, न = घोर + गवर + गफदिग + ग्सदिग

कोड जो प्रदर्शन की गणना के लिए जिम्मेदार है:

 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). 

मैं यह नोट करना चाहता हूं कि कार्यों में गणना और गणना_ बिंदु_ गुरुत्वाकर्षण, पूंछ पुनरावृत्ति का उपयोग नहीं किया जाता है, मुझे नहीं लगता कि यह किसी भी तरह प्रदर्शन या स्मृति की खपत को प्रभावित करेगा, इस तथ्य के कारण कि पुनरावृत्तियों की संख्या नगण्य है।

जब हमने प्रत्येक कोशिकाओं के लिए दक्षता गुणांक की गणना की है, तो हम सबसे बड़ा चुनते हैं:

 lists:max(calculate_point_gravity(PlayerMovesX , PlayerMovesY, AllVariants, Agress)). 

आप अभी भी यादृच्छिकता जोड़ सकते हैं, लेकिन मुझे यह अनावश्यक लगा।

निरीक्षण

कोई भी खेल दो पक्षों को परिभाषित किए बिना अपना अर्थ खो देता है: विजेता और हारने वाला, लेकिन कभी-कभी ड्रॉ के साथ विकल्प।

अब जीतने वाले चेक एल्गोरिथ्म की संक्षिप्त समीक्षा करें, प्रत्येक बाद के खिलाड़ी की बारी के बाद चेक को प्रारंभ किया जाता है, और मोड़ के क्रम में 3 परिणामों की जांच करता है: खिलाड़ी की जीत, बॉट की जीत, ड्रा, टेस्ट फ़ंक्शन इनपुट में 2 तर्क लेता है, 1 - खिलाड़ी द्वारा उठाए गए सभी कदम, 2 - अंतिम खिलाड़ी चाल।



मूल एल्गोरिथ्म को चित्र में दिखाया गया है (सभी दिशाओं में 8 किरणें हैं, यह संपीड़न के कारण दिखाई नहीं देता है) - वर्तमान प्रतीक के साथ सभी कोशिकाओं को देखने और काउंटर मूल्य में वृद्धि, लेकिन एक छोटी सी बारीकियों के साथ, 4 दिशाओं में से प्रत्येक को दो भागों में विभाजित किया गया है: ऊपरी और निचला। दोनों भागों की जाँच करने के बाद, हम जोड़ते हैं और एक जोड़ते हैं, यदि योग 5 है, तो जीतने का क्रम पाया जाता है।

बाकी

और हां, डेमो:

http://88.198.65.2:8000/

खेल की जटिलता गतिशील है, इसे अगली चाल तक बदला जा सकता है - डिफ़ॉल्ट रूप से - 0.8, अधिक से अधिक कठिनाई कारक - बॉट एक रक्षात्मक रणनीति में जाता है, कम - हमला करने की रणनीति, मैं आपको जटिलता के साथ प्रयोग करने की सलाह देता हूं, मेरी राय में, बॉट काफी अच्छी तरह से खेलता है [0.5] , १]।

मैं उन लोगों से पहले से माफी मांगता हूं जो एक प्रॉक्सी के पीछे हैं, या जिनका पोर्ट 8000 बंद है, मेरे पास अब गेम को पोर्ट 80 में ट्रांसफर करने का कोई तरीका नहीं है।

Github'e - github.com/Tremax/eTicTacToe पर उपलब्ध स्रोत

मैं क्लाइंट हिस्से पर विचार नहीं करता हूं, इस तथ्य के कारण कि वहां सब कुछ तुच्छ है।

संदर्भ

algolist.manual.ru/games/fiveinarow.php

आपकी प्रतिक्रिया सुनकर मुझे खुशी होगी।