Броя на вариантите в шаха

Всичко шахматно, на което не знаете мястото

by Advertising on Sun Nov 09, 2008 4:41 pm

Advertising
 

Броя на вариантите в шаха

Postby MIsterGo on Sun Nov 09, 2008 4:41 pm

Една тема, за която има най-различни наблюдения, да направим опит да сведем различните оценки?

Колко са вариантите (комбинациите) в шаха? Колко са възможните партии?
Нека първо напишем, това което е вече казано по въпроса в различните статии и книги.

Да отбележа, че има различни оценки: "повече от атомите във Галактиката"; "повече от атомите във Вселената"! Другият логичен въпрос: Как се изчисляват и колко са на брой атомите в Галактиката (Вселената)?
MIsterGo
Пешка
 
Posts: 18
Joined: Sat Nov 08, 2008 10:46 pm

by Advertising on Sun Nov 09, 2008 4:44 pm

Advertising
 

Re: Броя на вариантите в шаха

Postby Garnizov on Sun Nov 09, 2008 4:44 pm

Безброй! ;)
User avatar
Garnizov
Цар
 
Posts: 1551
Joined: Tue Mar 04, 2008 10:56 pm
Location: Pleven

by Advertising on Sun Nov 09, 2008 6:06 pm

Advertising
 

Re: Броя на вариантите в шаха

Postby atakurt on Sun Nov 09, 2008 6:06 pm

Изчисляват се със статистически метод, наричан "Монте Карло" - първо се изчисляват в единица обем и после се умножава полученото число по обема на даденото тяло, в случая - Вселената.
За удобство Архимед е приемал, че броят на атомите е 1 Гугъл = 1 000000..... (сто нули). Съвременната наука приема условно, че броят на атомите във Вселената е 1 Гугъл плекс = 1 000000...... (гугъл на брой нули).
Президент на ШК "Спартак" - Пловдив - viewtopic.php?f=41&t=921 . Гений и единствен официален представител на опозицията в българския шахмат! Родният шахмат не се ръководи правилно и затова върви надолу вече девета поредна година. РАЗРЕШАВАМ ВИ ДА ГОВОРИТЕ ЗА МЕН ВСИЧКО, КОЕТО ИСКАТЕ, ДОКАТО АЗ МОГА ДА ПРАВЯ ВСИЧКО, КОЕТО ИСКАМ!
User avatar
atakurt
Цар
 
Posts: 914
Joined: Tue Mar 18, 2008 12:43 pm
Location: София

Re: Броя на вариантите в шаха

Postby MIsterGo on Sun Nov 09, 2008 8:49 pm

Аха, благодаря.
Значи дискусията се разделя на два интересни клона: 1) Броят на вариантите в Шаха; 2) Броя на Атомите във Вселената.
А обединението, може да го кажем и така: Шахът е сътворен в "тази вселена", следователно може да има връзка между двете!?

Това за Архимед - в неговата книга "Изчисляване на броя на пясъчинките" ли беше, или нещо от този род?
Тогава следващият въпрос е как изчисляват обема на Вселената, защото на Галактиката се знае. Това беше свързано с годините живот на Вселената? Защото като живеем с Разширяваща се вселена - ключово е на колко години е тя - да знаем до колко се е разширила?
Само да не се стига до "омагьосан кръг" - ако знаем броя на годините, ще знаем обема; ако знаем обема - ще знаем броя на годините. Но може ли да знаем нещо със сигурност?
След това, дори ако знаем обема - трябва да знаем какво е "разпределението на веществото", защото със сигурност на едно място има повече, на друго място има по-малко.
MIsterGo
Пешка
 
Posts: 18
Joined: Sat Nov 08, 2008 10:46 pm

Re: Броя на вариантите в шаха

Postby sirkov-L on Mon Nov 10, 2008 11:53 am

Засега е сигурно едно: за разлика от привидно сходната игра шашки, която наскоро (2007 г.) бе "напълно изчислена", шахматът очевидно има доста повече на брой "варианти" (различни възможни пътища за развитие на една игра).

Ето линк към научното съобщение на изследователите от Университета в Албърта (Канада) за това как напълно са изчислили шашките
(които според тях имат 500 милиарда милиарда възможни позиции, т.е. 5 по 10 на степен 20)
http://www.sciencemag.org/cgi/content/abstract/1144079

Процесът е продължил около 18 години, като са използвали между 50 и 200 персонални компютъра.

Още информация за това докъде е стигнало изчисляването на други игри:
http://en.wikipedia.org/wiki/Perfect_play
Личният ми блог (в него публикувам информация и мнения по шахматни и други важни теми) е тук: http://sirkov.blogove.eu/
sirkov-L
Цар
 
Posts: 417
Joined: Mon Mar 10, 2008 2:03 pm

Re: Броя на вариантите в шаха

Postby Kalin on Mon Nov 10, 2008 12:21 pm

Това е много гадно - практически умира цялата игра... Tablebases могат да решат всеки проблем оттам нататък :(

Добре че шахът няма изчисляване ;)
За съжаление вече почти не се занимавам с шах, но ще запазя изключително хубави спомени от периода, в който се занимавах! Шахът помага във всички аспекти на живота и шахматистите са много приятни хора :)
В момента се занимавам с Интернет маркетинг и оптимизация на сайтове и предлагам хубава възможност за допълнителни доходи, която може да разгледате.
User avatar
Kalin
Цар
 
Posts: 2364
Joined: Sat Feb 23, 2008 7:56 pm
Location: Sofia, BG

Re: Броя на вариантите в шаха

Postby sirkov-L on Mon Nov 10, 2008 12:55 pm

Защо да умира цялата игра?
Винаги остава възможността да се състезаваме в чисто човешките си умения.

Тези въпроси вече са обсъждани в специализираните (шахматни и научни) издания, и аргументите, които се използват, са доста красноречиви: например това, че имаме "Формула 1", не означава, че конните надбягвания са станали по-малко интересни, нито пък че те самите са направили безпредметно поставянето на рекорди в бягането на 100 метра.
Last edited by sirkov-L on Mon Nov 10, 2008 1:21 pm, edited 1 time in total.
Личният ми блог (в него публикувам информация и мнения по шахматни и други важни теми) е тук: http://sirkov.blogove.eu/
sirkov-L
Цар
 
Posts: 417
Joined: Mon Mar 10, 2008 2:03 pm

Re: Броя на вариантите в шаха

Postby Kalin on Mon Nov 10, 2008 1:13 pm

Разбира се играта ще се запази на любителско ниво, но на професионално се съмнявам... Сравнението, което даваш, е доста неточно :)
За съжаление вече почти не се занимавам с шах, но ще запазя изключително хубави спомени от периода, в който се занимавах! Шахът помага във всички аспекти на живота и шахматистите са много приятни хора :)
В момента се занимавам с Интернет маркетинг и оптимизация на сайтове и предлагам хубава възможност за допълнителни доходи, която може да разгледате.
User avatar
Kalin
Цар
 
Posts: 2364
Joined: Sat Feb 23, 2008 7:56 pm
Location: Sofia, BG

Re: Броя на вариантите в шаха

Postby sirkov-L on Mon Nov 10, 2008 1:43 pm

Е, щом това сравнение ти се струва доста неточно, значи сигурно си готов с някое поне малко по-точно сравнение.

А който действително се интересува от въпроса, нека погледне следната публикация:
http://www.dit.unitn.it/~montreso/asd/docs/checkers.pdf
- съдържа доста конкретни числа, а е сравнително достъпно написана.
Личният ми блог (в него публикувам информация и мнения по шахматни и други важни теми) е тук: http://sirkov.blogove.eu/
sirkov-L
Цар
 
Posts: 417
Joined: Mon Mar 10, 2008 2:03 pm

Re: Броя на вариантите в шаха

Postby Kalin on Mon Nov 10, 2008 2:36 pm

Сравнението е неточно, защото карането на кола не ти помага да бягаш или яздиш, а знанието на оценката на всяка една позиция (което с ретроанализ неминуемо се постига при краен изчислен брой позиции) ще направи подготовката толкова определяща за резултата, че играта ще стане почти безмислена... Особено в игри, където няма реми. Шахът не е застрашен, понеже е неизчислим и освен това какво като ми кажат, че е4 и d4 водят до реми при правилна игра - това си го усещам и аз :D

Иначе благодаря за хубавите материали по темата :)
За съжаление вече почти не се занимавам с шах, но ще запазя изключително хубави спомени от периода, в който се занимавах! Шахът помага във всички аспекти на живота и шахматистите са много приятни хора :)
В момента се занимавам с Интернет маркетинг и оптимизация на сайтове и предлагам хубава възможност за допълнителни доходи, която може да разгледате.
User avatar
Kalin
Цар
 
Posts: 2364
Joined: Sat Feb 23, 2008 7:56 pm
Location: Sofia, BG

Re: Броя на вариантите в шаха

Postby sirkov-L on Mon Nov 10, 2008 2:47 pm

Примерът с автомобила, коня и тичането е във връзка с това, че ако си поставиш задача да стигнеш по най-бързия начин от точка А до точка Б, въпреки че вече разполагаме с доста други, технически решения за това, пак ни е интересно как отделен човек (без технически средства) се справя със същата задача.

Така и в шахмата: ако задачата е да се намери кой е най-добрият ход в дадена позиция, винаги ще е интересно как отделен човек стига до своето решение на този проблем, независимо че биха могли да съществуват и чисто технически решения на същата задача.
Личният ми блог (в него публикувам информация и мнения по шахматни и други важни теми) е тук: http://sirkov.blogove.eu/
sirkov-L
Цар
 
Posts: 417
Joined: Mon Mar 10, 2008 2:03 pm

Re: Броя на вариантите в шаха

Postby Bobbylon on Mon Nov 10, 2008 4:19 pm

MIsterGo wrote:Колко са вариантите (комбинациите) в шаха? Колко са възможните партии?
Нека първо напишем, това което е вече казано по въпроса в различните статии и книги.


Опит за обобщение на направените до момента изчисления е следното (исторически):
-1889 Кънингам неправилно изчислява, че след 4-ти ход, са възможни 71 782 позиции и 197 299 партии.
-1895 Мари посочва числото 71 870. (според Доусън 1946)
-1903 Мари коригира числото на вярната стойност 71 852. (според Фабел)
-1950 Клод Шанън (бащата на теория за информацията, както и на теорията за цифровите компютри), в известната си статия, поставила началото на компютърния шахмат, дава броя на валидните позиции, възникващи в партия от средно 40 хода: P(40) ~ 64! / [32!(8!)^2(2!)^6] ~ 10^43, която е и приетата днес долна граница на тази оценка. Причината е, че не са отчетени някои легални позиции, възникващи след взимане или превръщане при достигане на краен хоризонтал, докато някои невъзможни позиции, като пешки на първи/осми хоризонтал или едновременно шах и на двата царя, влизат в тази оценка... Разглежда се партия от 40 хода, тъй като средно около 40-ти ход става ясен изхода от партията и тогава най-често една от страните се предава. Типичната шахматна позиция притежава между 0 и 218 възможни хода, като средно ходовете са 30. Това число (30) е получено от Де Гроот при усредняване на данни за голям брой партии на майсторско ниво, където то оставало относително постоянно почти до техният край. По този начин след ход на белите, и следващ отговор от черните се получават средно 10^3 възможни позиции. Шанън оценява и нивото на сложност на шахмата на ~ 10^120 (английският термин е game-tree complexity) - отново долна граница. Това число е известно като Число на Шанън. Дава и оценка на времето, необходимото за изчисляване на първия ход от компютър, пресмятащ по 1 позиция за микросекунда (0.000001s): 10^90 години!
-1972 Бийлър дава за същото число оценка P(40) ~ 10^40, получено от броя пешечни позиции в случая на липса на вземане - 15^8, умножени по възможните фигурни позиции, разделени на 2 за двойките коне, топове и офицери - по понятни причини. Това число е неточно, поради липсата на отчитане за вземането от пешки, при което те променят вертикалите си (Шропел 1996).
-1990-те Виктор Алис дава горната граница за това число P(40) < 5х10^52, и оценява вярната стойност на близка до 10^50. Приемайки средната партия за 80 хода, и средния брой легални хода в една позиция за 35, той дава и нивото на сложност на шахмата ~ 10^123.
-1994 Шварцкоф обобщава броят на валидните позиции след 1, 2, 3, 4, 5, 6-ти ход: 20, 400, 5362, 71 852, 809 896, 9 132 484..., а броят на партиите, които приключват след съответния брой ходове са: 20, 400, 8902, 197 742, 4 897 256, 120 921 506, 3 284 294 545...
-1999 Харди дава оценка за броя възможни шахматни партии - (10^10)^50.

Сигурно има още пропуснати статии, но това общо взето е основното. 8-)

Връзки:
http://en.wikipedia.org/wiki/Chess#Math ... _computers
http://mathworld.wolfram.com/Chess.html
http://en.wikipedia.org/wiki/Shannon_number
http://en.wikipedia.org/wiki/Claude_Shannon
User avatar
Bobbylon
Цар
 
Posts: 631
Joined: Wed Apr 16, 2008 3:16 am
Location: София

Re: Броя на вариантите в шаха

Postby Bobbylon on Mon Nov 10, 2008 7:03 pm

MIsterGo wrote:Аха, благодаря.
Значи дискусията се разделя на два интересни клона: 1) Броят на вариантите в Шаха; 2) Броя на Атомите във Вселената.
А обединението, може да го кажем и така: Шахът е сътворен в "тази вселена", следователно може да има връзка между двете!?

Това за Архимед - в неговата книга "Изчисляване на броя на пясъчинките" ли беше, или нещо от този род?
Тогава следващият въпрос е как изчисляват обема на Вселената, защото на Галактиката се знае. Това беше свързано с годините живот на Вселената? Защото като живеем с Разширяваща се вселена - ключово е на колко години е тя - да знаем до колко се е разширила?
Само да не се стига до "омагьосан кръг" - ако знаем броя на годините, ще знаем обема; ако знаем обема - ще знаем броя на годините. Но може ли да знаем нещо със сигурност?
След това, дори ако знаем обема - трябва да знаем какво е "разпределението на веществото", защото със сигурност на едно място има повече, на друго място има по-малко.


Умишлено разделих коментара си на две, както правилно предложихте. Тъй като вторият въпрос пряко се отнася до материята, с която се занимавам професионално, ще си позволя по-широк коментар. Що се отнася до броя атоми във Вселената, според мен би било полезно да се внесат някои пояснения преди уточняване на тази оценка.
Съчинението на Архимед е с голяма историческа ценност, но за съжаление няма нищо общо с истинската стойност, която не би могла да бъде във възможностите за пресмятане дори и в най-смелите мечти на учените от Александрийската школа през третии век преди новата ера... ;)

За обем на Вселената като цяло не може да се говори. Ние (а и всеки друг наблюдател) сме в състояние да изследваме само ограничена област от нея, наречена Метагалактика - в границите на т.нар. космологичен хоризонт. Това е сфера с радиус разстоянието, което би могла да измине светлината за време, равно на възрастта на Вселената. Това е логично - от по-далечни обекти светлината не би имала време да достигне до нас. И тъй като нейната скорост е максималната възможна такава в природата, то за свойствата на областитте отвъд хоризонта можем само да предполагаме (по ефектите, които те оказват върху видимата Вселена), но не и да наблюдаваме. Дали е ограничена (крайна) или безкрайна Вселената - това не знаем, но разполагаме с информация за другите нейни основни характеристики (на Метагалактиката). Това са кривина на пространството, маса, плътност и разпределение на веществото и енергията, възраст, температура и т.н., вероятно валидни и за останалата невидима част. Възрастта е пресметната с помощта на различни методи, като след калибровката им е получена стойността 13.7 милиарда години (13.7 х 10^9). Това обаче не е радиусът на космологичния хоризонт в светлинни години. Причините се крият в ефектите на разширение - докато пътува, светлината трябва да премине през непрекъснато разширяващо се пространство, което я "носи" със себе си. Това увеличава радиуса на видимата Вселена на ~ 4.65 x 10^10 светлинни години. Той естествено нараства непрекъснато ;) Причината не е в разширението на Вселената, а просто защото с всяка година все по-далечни обекти стават видими, т.е. тя остарява. Друг интересен ефект е, че областите, които сега се намират на предела на видимата Вселена, по време на излъчване на светлината от тях, са били само на 36 милиона св.г. от материята, от която в последствие се е формирала Земята! Обемът е ясен - като знаем радиуса, лесно се изчислява (4 х 10^32 св.г. или 3 х 10^80 куб.м.).

Това беше за обема, сега за разширението. Без да изпадам в подробности, ще кажа следното. Разширява се пространството между обектите, като гравитационно свързаните структури се противопоставят на това разширение и остават стабилни. Такива структури са куповете от галактики, самите галактики, звездни купове, планетни системи и т.н. В по-голям мащаб тези структури (галактики и купове) се отдалечават едни от други по следния начин: колкото по-далече са два обекта, толкова по-бързо се отдалечават, т.е. толкова повече пространство има между тях, а то се разширява. Видимо всичко се разбягва от наблюдателя, без той да е център на Вселената - това е просто визуален ефект. Не си представяйте Вселената като балон, който се надува (нещо често срещано по учебниците) - макар и близко приближение, това не е точно така. Причината за разликата от една страна е, че примерът се отнася до двумерна повърхност в тримерно пространство (балон), което е различно от разширението на тримерно пространство. От друга страна, човек си представя началото на разширението (т.нар. Голям взрив) като експлозия (начало на надуване на балона) в една точка - център, и че всичко се отдалечава от него. Напротив - Вселената няма център и е "избухнала" едновременно във всички точки на пространството, което оттогава се и разширява. Този процес протича днес с определена скорост (~75 км/с на мегапарсек, 1 Мпс ~ 3.26 милиона св.г.), която не винаги е била еднаква. Според съвременните данни в началото е имало т.нар. фаза на инфлация - период на експоненциално разширение, последван от такъв на забавено разширение (с отрицателно ускорение), сменено преди няколко милиарда години от разширение с ускорение, като се предвижда нов период на експоненциално ускорение, водещ евентуално до разрушаване на свързаните структури. В съответствие с това, радиусът на видимата Вселена трябва да се коригира спрямо скоростта на разширение в различните епохи - през всяка от тях радиуса на хоризонта се променя по различен начин. Сумарният ефект е, че разширението е уголемило Вселената 1292 пъти от момента на излъчване на първото регистрирано лъчение.

И накрая веществото. Според последните данни, Вселената е плоска, т.е. пространството е евклидово, с изключение на пренебрежимите нееднородности около черните дупки. Вселената е изотропна, т.е. с еднакви свойства във всички посоки, и освен това хомогенна - с равномерно разпределение на веществото. Това е т.нар. Космологичен принцип - за мащаби над определена стойност (10 Мпс ~ 30 милиона св.г.) това е изпълнено. Под тези мащаби тя е йерархична - съществуват структури (най-големите са свръхкупове от галактики, подредени в нишки и стени, с огромни космически празнини между тях - подобно на пяна), т.е. има нехомогенно разпределение на веществото. Това са факти от изключителна важност - позволяват ни да пресметнем средната плътност на Вселената - 9.9 × 10^−27 kg/m^3 (доста малко число), както и да изградим подходяща теория за процесите, довели до настоящето състояние. А то е доста изненадващо: околко 3/4 от енергията във Вселената принадлежи на обект с неизяснена физическа същност - т.нар тъмна енергия; едва 1/4 се пада на материята (както знаем от уравнението на Айнщайн - на материята съответства енергия и обратно Е=mc^2). От своя страна материята се дели на тъмна (небарионна, изключително трудна за детектиране, тъй като не взаимодейства със светлината, а само гравитира) и светеща (барионна), като отношението им е 5:1, или от познатите ни атоми се състои само 4-5% от Вселената! Това е потресаващ факт довел до революция в Космологията (науката за еволюцията на Вселената като цяло) през последните десетина години. И така, от тези 4% материя, водородът заема 75%, хелият 23%, а всички останали елементи 2%. Това е резултат, получен от наблюдения, в съгласие с теорията за Първичния нуклеосинтез (част от т.нар. Стандартен модел на взаимодействията в природата) - протекъл в периода, когато Вселената е била млада, гореща и плътна. С изчислената средна плътност, и процентните съотношения, споменати по-горе, се получават средно по 0.27 атома водород на кубичен метър. За яснота ще кажем, че това в земни условия би бил невероятно дълбок вакуум! За Метагалактиката, спомената в началото, това прави 8 × 10^79 атоми. Всъщност по различни оценки това число варира между 4 × 10^79 и 10^81. Сравнете тези резултати с Числото на Шанън - 10^120... Разликата е 40 порядъка (не 40 пъти, а 40 степени на десятката, или нагледно - толкова нули...)!

Подобен резултат бихме получили и ако използваме факта, че около 300 000 години след Големия Взрив е протекъл процесът на рекомбинация, при който ядрата се свързват с електрони и формират нeутрални атоми, като при това се отделило огромно количество лъчение, достигнало до нас като Реликтов фон - ехо от раждането на Вселената. За настоящата епоха този фон е в микровълновия диапазон (пак поради ефектите на разширение), и съответства на температура 2.7 К (келвина), или ~ -270 C (целзий). Измервайки плътността на това лъчение, и отново използвайки Стандартния модел, можем да оценим масата на веществото, от което се е отделило то, и съответно броят атоми. Тук ще спомена и факта, че днешната материя съдържа само около една милиардна част от енергията, освободена при Големия взрив - останалата огромна част се е превърнала в лъчение, след анихилацията на материя и антиматерия в първите моменти на сътворението. Този процес изразява ефекта на т.нар. Нарушаване на симетрията в Стандартния модел, довело до т.нар. Барионен излишък - на всеки милиард частици антиматерия е имало милиард и една частици материя, съхранил достатъчно вещество за образуване на наблюдаваните днес структури.

За пълнота можем да кажем, че би могло да се тръгне и по друг път - да се изчислят атомите за даден обект (звезда, галактика), и да се обобщи за по-големи обеми. Това обаче е твърде неточен метод, тъй като се пропускат множество източници на атоми, а и се използват далеч не съвсем сигурни допускания и приближения. За любителите на сметките: масата на Слънцето (звезда от Главната последователност, т.е. типична звезда) е 2 × 10^30 kg, или ~ 10^57 атома водород; нашата Галактика съдържа 300-400 милиарда звезди (отново предположение, че тя е типична галактика, а и тук не смятаме междузвездния газ и прах), или 4 × 10^68 атома; броят галактики се оценява на 80-100 милиарда (тук пропускаме междугалактичния газ - значителна компонента), съдържащи 3-7 × 10^22 звезди, или 3 × 10^79 атома...
Last edited by Bobbylon on Tue Mar 09, 2010 7:10 am, edited 2 times in total.
User avatar
Bobbylon
Цар
 
Posts: 631
Joined: Wed Apr 16, 2008 3:16 am
Location: София

Re: Броя на вариантите в шаха

Postby MIsterGo on Tue Nov 11, 2008 12:35 pm

Сърдечно благодаря за великолепните материали по темата! :D

А специално обширните анализи на Bobbylon те оставят без дъх! Много яко! 8-)

Ще трябва време да се осмисли всичко това... :D
MIsterGo
Пешка
 
Posts: 18
Joined: Sat Nov 08, 2008 10:46 pm

Re: Броя на вариантите в шаха

Postby vano77 on Sat Jun 18, 2011 12:06 am

"Разбира се играта ще се запази на любителско ниво, но на професионално се съмнявам..."
дори да се изчисли до край играта, блица няма ли да си остане ?
vano77
Пешка
 
Posts: 5
Joined: Mon Feb 15, 2010 7:33 pm

Next

Return to Всичко за шаха

Who is online

Users browsing this forum: No registered users and 5 guests