{"id":2324,"date":"2010-08-31T02:30:09","date_gmt":"2010-08-31T00:30:09","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2324"},"modified":"2022-10-11T13:33:07","modified_gmt":"2022-10-11T11:33:07","slug":"chomp","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2010\/08\/31\/chomp\/","title":{"rendered":"Chomp"},"content":{"rendered":"

Se siete due golosi e non avete paura di impiastricciarvi le mani, potete provare questo gioco. Prendete una tavoletta di cioccolato di quelle formate da tanti quadretti, e alternatevi nello staccarne via un pezzo per mangiarvelo. L’unica regola da seguire \u00e8 che ciascun giocatore sceglie un quadretto e se lo mangia, insieme a tutti quelli rimasti al di sopra e alla destra. Attenzione, per\u00f2! Sul quadretto in basso a sinistra \u00e8 stato messo abbastanza Guttalax da far trascorrere un pomeriggio intero a dover scaricare l’intestino: colui al quale tocca prendere quel quadretto ha dunque perso la partita. Visto che un disegno vale pi\u00f9 di mille parole, dopo lo stacco c’\u00e8 un esempio pratico di partita, in cui il giocatore A, quello che inizia, perde la partita. Preferite giocare per primi o per secondi?<\/p>\n

\"Una<\/a>
Una partita a Chomp<\/figcaption><\/figure>Il gioco in questione si chiama Chomp<\/a>, ed \u00e8 stato chiamato cos\u00ec da David Gale, che l’ha (ri)scoperto nei primi anni ’70; ma gi\u00e0 nel 1952 Fred Schuh aveva proposto un gioco simile, con l’unica differenza che invece di quadretti di cioccolato venivano usati i divisori di un numero… roba molto meno dolce, insomma. Il gioco \u00e8 imparziale<\/i>, vale a dire che data una configurazione, ciascun giocatore – se tocca a lui giocare – ha a disposizione esattamente le stesse mosse (a differenza per esempio degli scacchi, in cui chi ha i pezzi bianchi non pu\u00f2 muovere quelli neri), e a informazione perfetta<\/i>, nel senso che ciascun giocatore sa esattamente cosa ha fatto l’avversario (a differenza per esempio del poker, in cui le carte dell’avversario sono ignote). Infine il gioco termina in un numero finito di mosse, e uno dei due giocatori deve per forza vincere: il pareggio non \u00e8 ammesso.<\/p>\n

Se si escludono i casi banali di tavolette lineari 1xn<\/i> – il primo giocatore mangia tutti i quadretti tranne uno – e forse di quelle 2xn<\/i>, non si conosce nessuna strategia esplicita che uno dei giocatori pu\u00f2 seguire per essere certo di giungere alla vittoria; il sistema pi\u00f9 semplice \u00e8 dare in pasto a un computer la posizione iniziale e fargli macinare un po’ i dati, per tirare fuori il manuale di istruzioni con la mossa giusta a seconda della configurazione. Il gioco sembrerebbe insomma non dico equo ma giocabile, e in effetti in pratica \u00e8 cos\u00ec. Ma i matematici sono degli esseri spregevoli che amano rovinare le sorprese, e hanno dimostrato che per una qualunque tavoletta con almeno due quadratini di cioccolato il primo giocatore ha la garanzia di poter sempre vincere!<\/p>\n

Il modo per provare tale risultato \u00e8 tipico della categoria dei matematici: una dimostrazione per assurdo, che non dice nulla di positivo ma si limita a tarpare le ali ai tentativi di trovare una risposta differente. In questo caso forse la cosa \u00e8 addirittura peggiore: vediamolo subito. Supponiamo infatti che il secondo giocatore abbia una strategia vincente; essa deve per definizione valere per qualunque mossa iniziale del primo giocatore, compresa quella minimale che consiste nel mangiarsi solo il quadretto in alto a destra. Se per\u00f2 ci pensate su un attimo, qualunque sia la risposta ottimale a quella mossa il primo giocatore avrebbe potuto farla subito lui: togliere quel singolo quadretto \u00e8 infatti una mossa neutra, nel senso che tutte le altre mosse lo tolgono. Insomma, il primo giocatore vince con la tecnica del furto di strategia<\/b> (“strategy stealing” in inglese). Cosa esattamente rubi non si sa, ma sicuramente ruba.<\/p>\n

\"\"<\/a>
un gioco con le uova<\/figcaption><\/figure>Sono parecchi i giochi a cui si pu\u00f2 applicare il furto della strategia: esempi classici sono quelli (imparziali e a informazione perfetta) in cui occorre completare una configurazione data prima dell’avversario, come il tris e il cinque-in-fila (su un foglio quadrettato occorre mettere cinque simboli in fila orizzonatale, verticale o diagonale). In questo caso si ragiona cos\u00ec: se il secondo giocatore avesse una strategia vincente, basta fare una prima mossa qualunque – che male non fa – e far finta di essere il secondo giocatore. Se mai nel corso della partita toccasse fare la mossa iniziale, basterebbe farne un’altra volta una a caso. In questi casi non \u00e8 garantita la vittoria, ma la patta almeno s\u00ec, come nel caso del tris: meglio che nulla. E non venitemi a chiedere “ma se anche il secondo giocatore fa una mossa a caso, per tornare ad essere il secondo?” Il punto \u00e8 proprio la strategia cercata non pu\u00f2 esserci!<\/p>\n

Termino lasciandovi con un giochino, “L’uovo di Colombo”. Immaginate di avere un tavolino rettangolare e un certo numero di uova, tutte uguali nella forma. Ogni giocatore posa un uovo sul tavolo, senza toccarne o spostarne nessun altro; il primo che non ha pi\u00f9 spazio per aggiungere un nuovo uovo ha perso. C’\u00e8 uno dei giocatori che ha a disposizione una strategia vincente? E se s\u00ec, \u00e8 anche possibile descriverla?<\/p>\n","protected":false},"excerpt":{"rendered":"

Chomp \u00e8 un gioco goloso in cui si mangia man mano una tavoletta di cioccolato. La strategia ottimale per giocarci \u00e8 sconosciuta, ma si sa chi vincer\u00e0 se entrambi gli avversari operano al loro meglio: uno dei soliti trucchetti dei matematici per dire le cose senza saperle.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2324","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/shh2yP-chomp","jetpack-related-posts":[{"id":190,"url":"https:\/\/xmau.com\/ilpost\/2010\/07\/16\/il-paradosso-di-san-pietroburgo\/","url_meta":{"origin":2324,"position":0},"title":"Il paradosso di san Pietroburgo","author":".mau.","date":"16\/07\/2010","format":false,"excerpt":"Da un banale gioco a testa o croce non solo si pu\u00f2 arrivare a una vincita potenzialmente infinita, ma addirittura la vincita media \u00e8 infinita!","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":184,"url":"https:\/\/xmau.com\/ilpost\/2010\/11\/13\/il-paradosso-di-penney\/","url_meta":{"origin":2324,"position":1},"title":"Il paradosso di Penney","author":".mau.","date":"13\/11\/2010","format":false,"excerpt":"In generale nei giochi a due persone \u00e8 chi fa la prima mossa a essere avvantaggiato; ma ci sono alcuni casi in cui \u00e8 meglio giocare per secondo, soprattutto se puoi conoscere in anticipo la prima mossa dell'avversario. E questo vale anche se si lancia una moneta!","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[con che probabilit\u00e0 vince il secondo giocatore?]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2010\/11\/penney-prob.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":192,"url":"https:\/\/xmau.com\/ilpost\/2010\/06\/24\/il-tennis-e-un-gioco-iniquo\/","url_meta":{"origin":2324,"position":2},"title":"Il tennis \u00e8 un gioco iniquo","author":".mau.","date":"24\/06\/2010","format":false,"excerpt":"Nel calcio, nel basket, e in tanti altri sport chi fa pi\u00f9 punti vince. Nel tennis non \u00e8 necessariamente cos\u00ec, ma si pu\u00f2 vincere anche con molti punti in meno: pi\u00f9 di quanto vi potreste aspettare","rel":"","context":"In \"attualit\u00e0\"","block_context":{"text":"attualit\u00e0","link":"https:\/\/xmau.com\/ilpost\/tag\/attualita\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2626,"url":"https:\/\/xmau.com\/ilpost\/2013\/07\/12\/epidemie\/","url_meta":{"origin":2324,"position":3},"title":"Epidemie","author":".mau.","date":"12\/07\/2013","format":false,"excerpt":"Un problema matematico la cui dimostrazione \u00e8 un'applicazione del concetto di monovariante.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":730,"url":"https:\/\/xmau.com\/ilpost\/2016\/03\/11\/siamo-stati-superati-dalle-macchine-anche-nel-go\/","url_meta":{"origin":2324,"position":4},"title":"Siamo stati superati dalle macchine anche nel Go?","author":".mau.","date":"11\/03\/2016","format":false,"excerpt":"Alla seconda vittoria consecutiva di AlphaGo contro il secondo giocatore mondiale, forse dobbiamo rifare i nostri conti","rel":"","context":"In \"go\"","block_context":{"text":"go","link":"https:\/\/xmau.com\/ilpost\/tag\/go\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2279,"url":"https:\/\/xmau.com\/ilpost\/2010\/06\/16\/vuvuzela-o-cara\/","url_meta":{"origin":2324,"position":5},"title":"Vuvuzela o cara","author":".mau.","date":"16\/06\/2010","format":false,"excerpt":"A quanto sembra la vera protagonista dei mondiali di calcio 2010 \u00e8 questa specie di trombetta di plastica. \u00c8 davvero impossibile eliminarla dalle telecronache?","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2324","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2324"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2324\/revisions"}],"predecessor-version":[{"id":2325,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2324\/revisions\/2325"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2324"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2324"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2324"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}