Branching factor

A red–black tree with branching factor 2

In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree. If this value is not uniform, an average branching factor can be calculated.

For example, in chess, if a "node" is considered to be a legal position, the average branching factor has been said to be about 35,[1][2] and a statistical analysis of over 2.5 million games revealed an average of 31.[3] This means that, on average, a player has about 31 to 35 legal moves at their disposal at each turn. By comparison, the average branching factor for the game Go is 250.[1]

Higher branching factors make algorithms that follow every branch at every node, such as exhaustive brute force searches, computationally more expensive due to the exponentially increasing number of nodes, leading to combinatorial explosion.

For example, if the branching factor is 10, then there will be 10 nodes one level down from the current position, 102 (or 100) nodes two levels down, 103 (or 1,000) nodes three levels down, and so on. The higher the branching factor, the faster this "explosion" occurs. The branching factor can be cut down by a pruning algorithm.

The average branching factor can be quickly calculated as the number of non-root nodes (the size of the tree, minus one; or the number of edges) divided by the number of non-leaf nodes (the number of nodes with children).

See also

References

  1. ^ a b Levinovitz, Alan (12 May 2014). "The Mystery of Go, the Ancient Game That Computers Still Can't Win". Wired. Retrieved 2014-06-02. The rate at which possible positions increase is directly related to a game's "branching factor," or the average number of moves available on any given turn. Chess's branching factor is 35. Go's is 250. Games with high branching factors make classic search algorithms like minimax extremely costly.
  2. ^ Laramée, François Dominic (6 August 2000). "Chess Programming Part IV: Basic Search". GameDev.net. Retrieved 2007-05-01.
  3. ^ Barnes, David. "What is the average number of legal moves per turn?". Chess Stack Exchange. Retrieved 2019-06-01.

Read other articles:

List of Shiva Temples in Pakistan

Shiva is a Hindu deity worshipped by Shaivaites in India as well as Pakistan as the destroyer of ignorance spread all across the universe. As one of the three main gods in the Hindu pantheon, there are temples dedicated to his worship in India and Pakistan as well (and abroad). The most prominent of these is the Jyotirlinga temples and Mellacheruvu Swayabhu Shambhulingeshwara Swami. In Shaivism, Shiva is the god of all and is described as worshipped by all, including Devas (gods) like Brahma...

 

 

De Christiana expeditione apud Sinas

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus.Artikel ini sebagian besar atau seluruhnya berasal dari satu sumber. Tolong bantu untuk memperbaiki artikel ini dengan menambahkan rujukan ke sumber lain yang tepercaya. De Christiana Expeditione apud Sinas, Augsburg, 1615. De Christiana expeditione apud Sinas suscepta ab Societate Jesu ... (Latin untuk Tentang Misi Kri...

 

 

الدوري البولندي الممتاز 1931

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يونيو 2019) الدوري البولندي الممتاز 1931 تفاصيل الموسم الدوري البولندي الممتاز  النسخة 11  البلد بولندا  المنظم �...

Parliament of Scotland

Legislature of the Kingdom of Scotland (1235–1707) This article is about the pre-1707 legislature. For the devolved legislative body established in 1999, see Scottish Parliament. Parliament of Scotland Pàrlamaid na h-AlbaPairlament o ScotlandRoyal Arms of Scotland (until 1603)TypeTypeUnicameral HistoryEstablishedc. 1235Disbanded1 May 1707Preceded byCuria regisSucceeded byParliament of Great BritainLeadershipLord High ChancellorThe Earl of Seafield1 since 1705 Seats2271Elect...

 

 

1819 en France

Chronologie de la France ◄◄ 1815 1816 1817 1818 1819 1820 1821 1822 1823 ►► Chronologies L'entrée du théâtre de l'Ambigu-Comique à une représentation gratis, Louis-Léopold Boilly, 1819.Données clés 1816 1817 1818  1819  1820 1821 1822Décennies :1780 1790 1800  1810  1820 1830 1840Siècles :XVIIe XVIIIe  XIXe  XXe XXIeMillénaires :-Ier Ier  IIe  IIIe Chronologies géographiques Afrique Afrique du Sud, Algérie, Angola, B...

 

 

Transports en Lituanie

Routes européennes traversant la Lituanie. Routes magistrales lituaniennes faisant partie du réseau transeuropéen de transport. Cet article fournit une vue d'ensemble de l'infrastructure des transports en Lituanie. Voies ferrées Article principal : Transport ferroviaire en Lituanie. On dénombre au total, en 2001, 1 998 km de voies ferrées, dont : 1 807 km de voies larges (de 1 524 mm), dont 122 km sont électrifiées ; 169 km de voi...

Giacomo Stucchi

Giacomo Stucchi Presidente della Lega LombardaDurata mandatodicembre 2017 –31 gennaio 2020 PredecessoreGiancarlo Giorgetti SuccessoreCarica cessata Presidente del COPASIRDurata mandato6 giugno 2013 –22 marzo 2018 PredecessoreMassimo D'Alema SuccessoreLorenzo Guerini Presidente della 14ª Commissione Affari Europei della Camera dei deputatiDurata mandato21 giugno 2001 –27 aprile 2006 PredecessoreLuigi Berlinguer SuccessoreFranca Bimbi Senatore de...

 

 

Camiguin

This article is about the Philippine province. For other uses, see Camiguin (disambiguation). Province in Northern Mindanao, PhilippinesCamiguinProvinceProvince of Camiguin(clockwise from top) Camiguin island satellite image in 2016, Ferry in Camiguin, Guinsiliban Port, and Mount Hibok-Hibok as seen from White Island FlagSealMotto: The Island Born of Fire[1]Location in the PhilippinesOpenStreetMapCoordinates: 9°10′N 124°43′E / 9.17°N 124.72°E / 9.1...

 

 

Associazione Sportiva Fidelis Andria 2002-2003

Questa voce sull'argomento stagioni delle società calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Voce principale: Associazione Sportiva Dilettantistica Fidelis Andria 1928. Associazione Sportiva Fidelis AndriaStagione 2002-2003Sport calcio Squadra Fidelis Andria Allenatore Vito Iosche poi Aldo Papagni Presidente Giuseppe Fuzio Serie C211º posto nel girone C. Maggiori presen...

Tai Daeng language

Tai language of Vietnam and Laos Tai DaengRed TaiTáy-Môc-ChâuꪼꪕꪵꪒꪉTay lɛɛŋTai Daeng written in Tai Viet scriptRegionNorthwestern VietnamNortheastern LaosEthnicityTai DaengNative speakers(105,000 cited 1999–2007)[1]Language familyKra–Dai TaiSouthwestern (Thai)Chiang SaenTai DaengWriting systemTai VietLanguage codesISO 639-3tyrGlottologtaid1249ELPTai DaengDistribution of the Southwestern Tai languages. Tai Daeng, Táy-Môc-Châu or Red Tai is the language of the Tai ...

 

 

Азиатский барсук

Азиатский барсук Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКласс:Мле�...

 

 

Enemies of the State

2020 American filmEnemies of the StateTheatrical release posterDirected bySonia KennebeckProduced by Ines Hoffman Kanna Sonia Kennebeck CinematographyTorsten LappEdited byMaxine GoedickeMusic byInsa RudolphProductioncompanies Codebreaker Films Reva & David Logan Foundation International Documentary Association Chicken & Egg Pictures JustFilms/Ford Foundation Distributed byIFC FilmsRelease dates September 11, 2020 (2020-09-11) (TIFF) July 30, 2021 (202...

周處除三害 (電影)

周處除三害The Pig, The Snake and The Pigeon正式版海報基本资料导演黃精甫监制李烈黃江豐動作指導洪昰顥编剧黃精甫主演阮經天袁富華陳以文王淨李李仁謝瓊煖配乐盧律銘林孝親林思妤保卜摄影王金城剪辑黃精甫林雍益制片商一種態度電影股份有限公司片长134分鐘产地 臺灣语言國語粵語台語上映及发行上映日期 2023年10月6日 (2023-10-06)（台灣） 2023年11月2日 (2023-11-02)（香�...

 

 

جائزة بيتينا فون أرنيم

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (ديسمبر 2018) يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها...

 

 

التدخل العسكري الروسي في الحرب الأهلية السورية

التدخل العسكري الروسي في الحرب الأهلية السورية جزء من الانخراط الروسي في الحرب الأهلية السورية التدخل العسكري ضد تنظيم الدولة الإسلامية الحرب الأهلية السورية طائرتي سوخوي سو-25 هجوميتان في مطار باسل الأسد الدولي باللاذقية معلومات عامة التاريخ 30 سبتمبر 2015 – جاري (8 سنواتٍ ...

منتخب قيرغيزستان لاتحاد الرغبي للسيدات

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يوليو 2019) هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسي...

 

 

Paolo Ferrari (actor)

Italian actor (1929–2018) Paolo FerrariFerrari in 1961Born(1929-02-26)26 February 1929Brussels, BelgiumDied6 May 2018(2018-05-06) (aged 89)Rome, ItalyOccupation(s)Actor, voice actor, television presenterYears active1938-2018Height1.70 m (5 ft 7 in)Spouses Marina Bonfigli(m. 1956; div. 19??) Laura Tavanti ​(m. 1970)​ Children3, including Fabio Ferrari Paolo Ferrari (26 February 1929 – 6 May 2018) was an Italian actor, voice actor an...

 

 

Irving Babbitt

American journalist Irving BabbittBorn(1865-08-02)August 2, 1865Dayton, OhioDiedJuly 15, 1933(1933-07-15) (aged 67)Cambridge, MassachusettsEducationHarvard CollegeOccupation(s)Academic, literary criticSpouse Dora May Drew ​(m. 1900)​Children2 This article is part of a series onConservatismin the United States Schools Compassionate Fiscal Fusion Libertarian Moderate Movement Neo Paleo Progressive Social Traditionalist Principles American exceptionalism Anti-co...

Easter Rising

1916 armed insurrection in Ireland This article is about the armed insurrection in Ireland. For the musical, see Easter Rising (musical). Easter RisingÉirí Amach na CáscaPart of the Irish revolutionary periodO'Connell Street, Dublin, after the Rising. The GPO is at left, and Nelson's Pillar at right.Date24–29 April 1916LocationMostly Dublin; skirmishes in counties Meath, Galway, Louth, Wexford, CorkResult Unconditional surrender of rebel forces, execution of most leadersBelligerents Iris...

 

 

Second Polish Republic

Country in Central and Eastern Europe (1918–1939) Republic of PolandRzeczpospolita Polska (Polish)1918–1939 Flag(1928–1939) Coat of arms(1928–1939) Anthem: Mazurek Dąbrowskiego(English: Poland Is Not Yet Lost)(1927–1939)The Second Polish Republic in 1930Administrative divisions of the Second Polish Republic in 1930Capitaland largest cityWarsaw52°13′48″N 21°00′40″E / 52.23000°N 21.01111°E / 52.23000; 21.01111Official languagesPolish...