هندسه زبانشناختی - ویکیپدیا، دانشنامهٔ آزاد
هندسهٔ زبانشناختی (LG)، ارائه روشی جدید در حل مسائل با ابعاد بالا در سیستمهای چندعامله است. هندسه زبانشناختی بهطور کلی یک روش حل مناسب برای این مسائل در حالتی که بازیهای تختهای در میان آنها تعریف شود، ارائه میدهد. به زبان سادهتر هندسه زبانشناختی در واقع ابزاری برای سادهتر کردن جستجو در میان استراتژیهای موجود است. قدرت محاسباتی هندسه زبانشناختی بر اساس استفاده از فناوری هوشمند توسعه داده شده توسط متخصصان میباشد که در زمیته سیستمهای کنترلی خاص و پیچیده بسیار موفق عمل کردهاست. با این وجود، در مقابل سایر رویکردها بر مبنای ایده «دو عامل رقابت»، این فناوری هوشمند سبب شدهاست تا جوهره ریاضیاتی هندسه زبانشناختی بسیار پیچیده شده و نتیجتاً کمتر واضح به نظر برسد.[۱] همین پیچیدگی سبب شدهاست تا تحقیقات در حوزه هندسه زبان شناختی تاکنون محدود بماند. پیشرفتهترین کاربرد استفاده از هندسه زبانشناختی تاکنون، استفاده از آن در پروژه LG-RAID (هندسه زبانشناختی- تصمیمگیری در لحظه و کار اطلاعاتی خصمانه)، مربوط به پروژه عظیم دارپا (سازمان پروژههای تحقیقاتی پیشرفتهٔ دفاعی) با نام DARPA-RAID میباشد که یک سیستم استدلالی خصمانه را توسعه میدهد.[۲]
کاربرد هندسه زبان شناختی
[ویرایش]LG بهطور چشمگیری اندازه درختهای جستجو را کاهش داده و در نتیجه مسائل را از لحاظ محاسباتی قابل لمس میکند. LG بهعنوان یک فنآوری هوشمند، جستجو را با ساختوساز استراتژیهای مختلف جایگزین میکند و یک بیان رسمی و مجرد از یافتههای جستجوی خبره فراهم میکند. استراتژیهای خبره رسمی، منجر به الگوریتمهای کارآمدی برای تنظیمات مسئله میشود که ابعاد این تنظیمات ممکن است بهطور چشمگیری بزرگتر از ابعادی باشد که نخبگان استراتژیهای خود را بر آن اساس توسعه دادهاند. علاوه بر آن، این استراتژیهای رسمی مجازند که مسائل را در حوزههایی مختلف بسیار فراتر از نواحی پیشبینیشده توسط نخبگان حل کنند. این مسئله بسیار شگفتانگیز است که برای کلاسهای خاصی از مسائل، این استراتژیهای نخبه، منجر به جوابهای شبه بهینه میشود. برای فرموله کردن این فنآوری هوشمند، LG از تئوری زبانهای رسمی (یعنی زبانشناسی رسمی) و همچنین ساختارهای هندسی مشخصی در تخته مجرد (بازی که مبنای آن بخت و اقبال نمیباشد) استفاده میکند. با توجه به اینکه هر دوی زبانشناسی و نیز هندسه در این زمینه درگیر هستند، این رویکرد، هندسه زبانشناختی نامگذاری شدهاست. در روش LG، سلسله مراتب زیرسیستمها توسط سلسله مراتب زبانهای رسمی بیان میشود. یعنی همان سلسله مراتبی که برای تعریف ساختار یک زبان از حروف تا کلمات استفاده شدهاست، در LG نیز در نظر گرفته میشود. همانطور که کوچکترین عضو تشکیلدهنده یک زبان حروف هستند، در LG نیز این کوچکترین عنصر تشکیلدهنده، سمبلها هستند.
مفهوم هندسه زبان شناختی
[ویرایش]LG از تئوری زبانهای رسمی (یعنی زبانشناسی رسمی) و همچنین ساختارهای هندسی مشخصی دربازی تخته انتزاعی (ABG) استفاده میکند. با توجه به اینکه هردوی زبانشناسی و نیز هندسه در این زمینه درگیر هستند، این رویکرد، هندسه زبانشناختی نامگذاری شدهاست. در روش LG، سلسلهمراتب زیرسیستمها توسط سلسلهمراتب زبانهای رسمی بیان میشود. یعنی همان سلسله مراتبی که برای تعریف ساختار یک زبان از حروف تا کلمات استفادهشدهاست، در LG نیز در نظر گرفته میشود. همانطور که کوچکترین عضو تشکیلدهنده یک زبان حروف هستند، در LG نیز این کوچکترین عنصر تشکیل دهنده، نمادها هستند. در ادامه مطالعات پیشین در زمینه هندسه زبانشناختی مرور شدهاند.
تخمینزده میشود که شطرنج دارای ۱۰۴۳ موقعیت قانونی باشد[۳] کلود شانون مهندس برق، ریاضیدان و پدر تئوری اطلاعات برای نخستینبار پیچیدگی درختبازی شطرنج را محاسبه کرد و به عدد ۱۰۱۲۰ رسید. یعنی در هر بازی شطرنج بهطور متوسط ۱۰۱۲۰ بازی با توجه به حرکات بازیکنان انجام میگیرد. این عدد به شمارهٔ شانون معروف است.[۴]
مسئلهٔ دانههای گندم یکی از مسائل ریاضی مربوط به شطرنج است. روزی خواجهای در مسابقهای برندهشد و شاهزادهٔ جوان که به تازگی شاه شده بود، گفت که هرچه خواجه بخواهد به او میدهد. خواجه گفت که یک دانهٔ گندم و یک صفحهٔ شطرنج میخواهد. فقط شاه باید هر روز دو برابر دانههای بیشتر به او بدهد تا ۶۴ روز (تعداد خانههای شطرنج) به پایان برسد. یعنی در روز نخست یکدانه، در روز دوم دو دانه، در روز سوم چهار دانه و به همین ترتیب تا ۶۴ روز به پایان برسد و در پایان تعداد دانهها دوباره دو برابر میشد. طبق محاسبات ذهنی این بازی، در روز ۶۴اُم، تعداد دانههای گندم بهشمار ۱۸٬۴۴۶٬۷۴۴٬۰۷۳٬۷۰۹٬۵۵۱٬۶۱۵ رسید که اصلاً این تعداد دانه ی گندم در زمین وجود نداشت.[۵]
در سال ۱۹۵۰، نخستین برنامهٔ شطرنج رایانه توسط آلن تورینگ انگلیسی نوشته شد، برنامهٔ او برای رقابت با بازیکنان شطرنج بسیار ضعیف بود. با این حال، این برنامه نشانداد که رایانه میتواند در بازی شطرنج با انسان رقابت کند. در همان سال، کلود شانون طرح بهتری برای اقدام رایانه به بازی شطرنج ارائه داد. در سال ۱۹۵۸، برنامهٔ شطرنج برای نخستین بار یک انسان را شکست داد.[۶]
همانطور که اشاره شد تاریخ استفاده از کامپیوتر در شطرنج توسط مقالهای در سال ۱۹۵۰ شروع شد که در آن یک چارچوب برای توسعه بیشتر این بازی معرفی شد.[۷] با استفاده از روشهای جستجوی فراگیر (خام و بیخردانه) [1] که روشهابی است که در آن تمام حالات ممکن تا رسیدن به جواب بررسی میگردد وبهسرعت کامپیوتربهشدت وابسته بودند، برنامههای شطرنج کامپیوتر بهتدریج و با پیشرفت کامپیوترها سطح بازی خود را افزایش دادند.[۸] در نهایت و با توسعه این برنامهها در میانه دهه ۹۰ میلادی، این برنامهها به سطحی معادل با یک استاد بزرگ در شطرنج رسیدند. در سال ۱۹۷۰، نخستین مسابقات قهرمانی بزرگ شطرنج رایانه به نام قهرمانی شطرنج رایانه آمریکای شمالی توسط انجمن ماشینهای حسابگر برگزار شد. شطرنج دانشگاه نورثوسترن قهرمان این جام شد.[۹] در ۱۱ مه ۱۹۹۷،[۱۰] واقعه تاریخی مهمی رقم خورد سیستم شطرنج کامپیوتری آبی تیره[2] که رایانهای ساختهٔ شرکت IBM بود، توانست در ۶ بازی قهرمان جهان،گری کاسپاروف را شکستدهد.[۱۱] دو برد سهم آبی تیره و یک برد سهم کاسپاروف بود و سه بازی دیگر مساوی شد. این نخستین باری بود که قهرمان شطرنج جهان از یک رایانه شکستخورد.[۱۲] بعد از این واقعه بود که شطرنج کامپیوتر جذابیت خود را کمکم از دست داد.
تمام یپیشرفتهای عمده در این زمینه ازجمله پیروزی برنامه آبی تیره، ناشی از روش جستجوی فراگیر است. اما سؤال اساسی این است که چگونه میتوان از این مزایا برای مسائل مختلف دیگر بهویژه در حل مسائلی با ابعاد بسیار بالاتر و نه فقط شطرنج بهره برد. پاسخ این است که این امکان به صورت کامل وجود ندارد! حتی در آینده نیز حل این مسائل با استفاده از روش جستجوی فراگیر امکانپذیر نخواهد بود. در واقع رویکرد یک استاد بزرگ (تقریباً بدون هیچ جستجویی) هنوز کشف نشدهاست. یعنی بدون جستجو نمیتوان همانند یک استاد بزرگ شطرنجبازی کرد. بعد از واقعه ۱۹۹۷ این امر مهمتر از قبل مورد توجه قرار گرفت که شطرنج را میتوان با نگاه هوش محاسباتی و نه فقط یک مسابقه مدنظرقرارداد.[۱۳]
در واقع باید گفت که همهٔ تحقیقات انجامشده درزمینه شطرنج کامپیوتری هم در جهت استفاده از روش جستجوی فراگیر نبودند. در دهههای ۷۰ و ۸۰ میلادی پروژهای با عنوان "پیشگام [3]" با همکاری قهرمان سابق شطرنج جهان میخائیل بوتوینیک در روسیه کلید خورد. او در کتاب خود با عنوان کامپیوتر در شطرنج مینویسد که روش جستجوی فراگیر بهراحتی سازگار با پیشرفتهای بعدی نیست و حال نوبت استفاده از کامپیوتر برای سازگاری با روشهای ثمربخشتر دیگر است. او در این کتاب تأکید کرد که ممکن است پروژه "پیشگام" در این زمینه موفق باشد ک یا نباشد، اگر این روش ناموفق بود، حداقل اثبات خواهد شد که قطعاً روش دیگری وجود دارد که میتواند مسئله را حل کند.[۱۴]
در سالهای بعد بوریس استیلمن در کتاب خود روشی نوین با عنوان هندسه زبانشناختی را معرفی کرد و آن را جایگزینی مناسب برای پروژه «پیشگام» دانست.[۱۵] او در کتاب خود، با ارائه آزمایشهای مختلف، نوید ایدههای جدید در این زمینه میدهد.
هندسه زبانشناختی، در حل بازیهای تختهای با دو بازیکن و نیز بازیهای جنگی بهخوبی قابل استفاده است. در این روش، سیستم یا مسئله به تعدادی زیرسیستم تقسیم میشود که در هر یک عنصر اصلی و مسیر آن (که به آن تراجکتوری اصلی گفته میشود) شناختهشده هستند. سپس، یک شبکه متشکل از تراجکتوریها ایجاد میشود. در مقایسه با سایر روشها و استراتژیهای جستجو، LG نشان داده است که در حل مسائلی که در آنها اندازه خیلی بزرگ است؛ با جستجویی عمیقتربهصورت بلادرنگ یا نزدیک به بلادرنگ بسیار موفق بودهاست.[۱۶] در نهایت با جستجو در زیرسیستمها و توسط یک روش جستجو، جواب یافت خواهد شد.
LG یک رویکرد تئوریبازی برای حل مسائل با ابعاد و سایز بزرگ بهصورت بلادرنگ است.[۱۷] این روش شامل ابزاری برای بازنمایی دانش در سیستمهای پیچیده چند عامله است.[۱۵]
شروع اصلی ایده هندسه زبانشناختی در درجه اول متعلق به دهه ۶۰ میلادی و توسط قهرمان سابق شطرنج میخائیل بوتوینیک و سپس دهه ۷۰ در همکاری با استیلمن در پروژه موسوم به پیشگام بودهاست.[۱۸]
هدف از این پروژه این بود که اولاً بهصورت ریاضی روشهای استفاده شده در شطرنج فرموله شوند که توسط آنهاو بدون استفاده از عملیات جستجو بتوان مسئله شطرنج را حل کرده و برنده شد. دوماً اینکه آیا این روش در سایر مسائل پیچیدهای که در آنها از روشهای مختلف جستجو استفاده میشده قابل استفاده است یا خیر؟. در ادامه، استیلمن این روش را در طول ۴۰ سال بعد به یک ابزار تکامل یافته در حل مسائل سخت در صنعت و بخصوص حوزههای نظامی تبدیل کرد.[۱۹]
درواقع، استیلمن پایههای یک ایده جدید را در دهه ۱۹۸۰ توسعه داده و اولین بار در سال ۱۹۹۱ در دانشگاه مک گیل بود که از عبارت «هندسه زبانشناختی» در توصیف این روش و ایده جدید در حل مسائل تختهای استفاده کرد.[۲۰] کلمه «زبانشناختی» در هندسه زبانشناختی به سلسله مراتب زبانهای رسمی اشاره دارد که در واقع بیانکننده حالت عاملها، شبکههای سیستم و جستجو برای یافتن یک استراتژی برنده است. لغت «هندسه» نیز به پیکرهبندی بازی بهعنوان یک بازی که بهصورت تختهای مدل شدهاست اشاره دارد.
در حال حاضر گروههای تحقیقاتی محدودی در سرتاسر دنیا بر روی هندسه زبانشناختی به تحقیق و پژوهش مشغول هستند. در ایران، دکتر الیپس مسیحی، عضو هیئت علمی سابق دانشگاه تربیت مدرس و عضو هیئت علمی فعلی دانشگاه پلی تکنیک کالیفرنیا در پمونا آمریکا به همراه تیم تحقیقاتی خود متشکل از یک دانشجوی دکترا (احمد الهیاری) و یک دانشجوی کارشناسی ارشد (علیرضا مداحی) پژوهشهایی را پیرامون این موضوع انجام داده و میدهند.
[1]Brute-force search
[2]Deep Blue
[3]PIONEER
[4]Thought experiments and visual streams
منابع
[ویرایش]- ↑ Yakhnis, V. , Stilman, B. Foundations of Linguistic Geometry: Complex Systems and Winning Conditions, Proceedings of the First World Congress on Intelligent Manufacturing Processes and Systems (IMP&S), Feb. (1995)
- ↑ DARPA RAID program, IPTO, 2004-08, http://www.darpa.mil/ipto/programs/raid/raid.asp
- ↑ “number of legal chess positions”. Mathematik.uni-bielefeld.de. Archived from the original on 20 March 2013. Retrieved 15 March 2013
- ↑ “The number of Shannon”. Chessdom.com, 15 April 2007. Archived from the original on 20 March 2013. Retrieved 15 March 2013.
- ↑ “The Legend of the Chessboard”. Camosun.bc.ca. Archived from the original on 24 March 2013. Retrieved 21 March 2013.
- ↑ “An Introduction to Computer Chess”. Uwaterloo.ca. Archived from the original on 20 March 2013. Retrieved 17 March 2013.
- ↑ Shannon, C.E. (1950). Programming a digital computer for playing chess, Philosophy Magazine, March, (356-375), 41.
- ↑ Newborn, M. (1996). Computer Chess Comes of Age, Springer-Verlag, New York, NY.
- ↑ “The Development of Computer Chess”. Mark-weeks.com. Archived from the original on 20 March 2013. Retrieved 17 March 2013.
- ↑ “Deep Blue”. IBM.com. Archived from the original on 20 March 2013. Retrieved 17 March 2013.
- ↑ “Garry Kasparov vs Deep Blue”. Chessgames.com. Archived from the original on 20 March 2013. Retrieved 17 March 2013.
- ↑ “In Their Words”. IBM.com. Archived from the original on 20 March 2013. Retrieved 17 March 2013.
- ↑ McCarthy, J. (1990). Chess as the Drosophila of AI, in Computers, Chess, and Cognition, Ed. by Marsland, T.A. , Shaeffer, J. , (227-237), Springer-Verlag, New York.
- ↑ Botvinnik, M.M. , (1984). Computers in Chess: Solving Inexact Search Problems. Springer Series in Symbolic Computation, with Appendixes, Springer-Verlag: New York (Translated from Russian into English), 158 pp.
- ↑ ۱۵٫۰ ۱۵٫۱ B. Stilman, Linguistic Geometry: From search to construction, Kluwer Academic Publisher (now Springer), 2000.
- ↑ Stilman, B. , 2012. Discovering Components of the Primary Language. In Intelligent Systems Design and Applications IEEE, pp. 7-12.
- ↑ Stilman, B. , 2013. Discovering the Discovery of Linguistic Geometry. International Journal of Machine Learning and Cybernetics, 4(6), pp. 575-594.
- ↑ ] Botvinnik, M.M. , (1984). Computers in Chess: Solving Inexact Search Problems. Springer Series in Symbolic Computation, with Appendixes, Springer-Verlag: New York (Translated from Russian into English), 158 pp.
- ↑ Umanskiy, O. , Boyd, R. , Pugachev, V. , Hagen, L. , Yakhnis, V. and Stilman, B. , 2012. Industrial Application of Linguistic Geometry. 12th International Conference on Intelligent Systems Design and Applications (ISDA).
- ↑ Boris Stilman , Vladimir Yakhnis , Oleg Umansky, Winning strategies for robotic wars: defense applications of linguistic geometry, Artif Life Robotics (2000) 4:148-155