226:. This principle changes the representation of the game to the more basic version of the bamboo stalks. The last possible set of graphs that can be made are convergent ones, also known as arbitrarily rooted graphs. By using the fusion principle, we can state that all vertices on any cycle may be fused together without changing the value of the graph. Therefore, any convergent graph can also be interpreted as a simple bamboo stalk graph. By combining all three types of graphs we can add complexity to the game, without ever changing the nim sum of the game, thereby allowing the game to take the strategies of Nim.
466:
82:
27:
213:
In the impartial version of
Hackenbush (the one without player specified colors), it can be thought of using nim heaps by breaking the game up into several cases: vertical, convergent, and divergent. Played exclusively with vertical stacks of line segments, also referred to as bamboo stalks, the game
72:
assumption that the game can be finished in a finite amount of time, provided that there are only finitely many line segments directly "touching" the ground. On an infinite board, based on the layout of the board the game can continue on forever, assuming there are infinitely many points touching
53:
The game starts with the players drawing a "ground" line (conventionally, but not necessarily, a horizontal line at the bottom of the paper or other playing area) and several line segments such that each line segment is connected to the ground, either directly at an endpoint, or indirectly, via a
124:: Each line segment is colored either red or blue. One player (usually the first, or left, player) is only allowed to cut blue line segments, while the other player (usually the second, or right, player) is only allowed to cut red line segments.
115:
All line segments are the same color and may be cut by either player. This means payoffs are symmetric and each player has the same operations based on position on board (in this case structure of drawing). This is also called Green
106:, meaning that the options (moves) available to one player would not necessarily be the ones available to the other player if it were their turn to move given the same position. This is achieved in one of two ways:
209:
to each vertex that lies on the ground (which should be considered as a distinguished vertex — it does no harm to identify all the ground points together — rather than as a line on the graph).
136:
Blue-Red
Hackenbush is merely a special case of Blue-Red-Green Hackenbush, but it is worth noting separately, as its analysis is often much simpler. This is because Blue-Red Hackenbush is a so-called
234:
The Colon
Principle states that when branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum. Consider a fixed but arbitrary graph,
132:: Each line segment is colored red, blue, or green. The rules are the same as for Blue-Red Hackenbush, with the additional stipulation that green line segments can be cut by either player.
68:
many (in the case of a "finite board") or infinitely many (in the case of an "infinite board") line segments. The existence of an infinite number of line segments does not violate the
57:
On their turn, a player "cuts" (erases) any line segment of their choice. Every line segment no longer connected to the ground by any path "falls" (i.e., gets erased). According to the
585:
182:, and many more general values that are neither. Blue-Red-Green Hackenbush allows for the construction of additional games whose values are not real numbers, such as
459:
that keeps the
Sprague-Grundy values the same. In this way you will always have a reply to every move he may make. This means you will make the last move and so win.
353:
have the same
Sprague-Grundy value is equivalent to the claim that the sum of the two games has Sprague-Grundy value 0. In other words, we are to show that the sum
465:
162:
87:
516:
54:
chain of other segments connected by endpoints. Any number of segments may meet at a point and thus there may be multiple paths to ground.
664:
222:
stating that when branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their
561:
528:
659:
218:
and can be directly analyzed as such. Divergent segments, or trees, add an additional wrinkle to the game and require use of the
669:
634:
674:
654:
99:
523:. Mathematical Sciences Research Institute Publications. Vol. 29. Cambridge University Press. pp. 61–78.
151:
69:
20:
603:
58:
198:
521:
Games of No Chance: Papers from the
Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994
620:
156:
94:
In the original folklore version of
Hackenbush, any player is allowed to cut any edge: as this is an
150:
Hackenbush has often been used as an example game for demonstrating the definitions and concepts in
206:
202:
166:
by some of the founders of the field. In particular Blue-Red
Hackenbush can be used to construct
599:
579:
183:
38:
260:
be arbitrary trees (or graphs) that have the same
Sprague-Grundy value. Consider the two graphs
567:
557:
524:
556:. Conway, John H. (John Horton), Guy, Richard K. (2nd ed.). Natick, Mass.: A.K. Peters.
102:. Thus the versions of Hackenbush of interest in combinatorial game theory are more complex
538:
534:
171:
367:
is a P-position. A player is guaranteed to win if they are the second player to move in
339:
have the same
Sprague-Grundy value. Consider the sum of the two games. The claim that
179:
167:
95:
142:, which means, essentially, that it can never be an advantage to have the first move.
648:
103:
194:
42:
175:
81:
65:
26:
571:
491:
138:
61:
of combinatorial game theory, the first player who is unable to move loses.
98:
it is comparatively straightforward to give a complete analysis using the
471:
An instance in which the game can be reduced using the Colon Principle
174:, while the values of infinite Blue-Red Hackenbush boards account for
417:
are not disturbed.) If the first player moves by chopping an edge in
223:
187:
45:
connected to one another by their endpoints and to a "ground" line.
385:
in one of the games, then the second player chops the same edge in
639:
80:
25:
215:
381:. If the first player moves by chopping one of the edges in
19:
For the Groucho Marx character, Hugo Z. Hackenbush, see
316:
represents the graph constructed by attaching the tree
445:
are no longer equal, so that there exists a move in
389:
in the other game. (Such a pair of moves may delete
170:: finite Blue-Red Hackenbush boards can construct
85:A blue-red Hackenbush girl, introduced in the book
41:. It may be played on any configuration of colored
331:. The colon principle states that the two graphs
193:Further analysis of the game can be made using
37:is a two-player game invented by mathematician
8:
584:: CS1 maint: multiple names: authors list (
197:by considering the board as a collection of
30:A starting setup for the game of Hackenbush
554:Winning ways for your mathematical plays
163:Winning Ways for Your Mathematical Plays
88:Winning Ways for your Mathematical Plays
482:
461:
577:
154:, beginning with its use in the books
7:
640:Hackenbush on Pencil and Paper Games
431:, then the Sprague-Grundy values of
519:. In Nowakowski, Richard J. (ed.).
552:R., Berlekamp, Elwyn (2001–2004).
238:, and select an arbitrary vertex,
14:
635:Hackenstrings, and 0.999... vs. 1
64:Hackenbush boards can consist of
624:, 2nd edition, A K Peters, 2000.
464:
16:Mathematical pen-and-paper game
403:from the games, but otherwise
1:
691:
18:
665:Combinatorial game theory
152:combinatorial game theory
129:Blue-Red-Green Hackenbush
21:A Day at the Races (film)
515:Guy, Richard K. (1996).
230:Proof of Colon Principle
660:Abstract strategy games
172:dyadic rational numbers
670:Paper-and-pencil games
100:Sprague–Grundy theorem
91:
59:normal play convention
31:
492:"What is Hackenbush?"
84:
29:
621:On Numbers and Games
157:On Numbers and Games
112:Original Hackenbush:
600:Ferguson, Thomas S.
121:Blue-Red Hackenbush
675:John Horton Conway
655:Mathematical games
205:and examining the
92:
39:John Horton Conway
32:
517:"Impartial games"
214:directly becomes
682:
618:John H. Conway,
611:
610:
608:
596:
590:
589:
583:
575:
549:
543:
542:
512:
506:
505:
503:
502:
487:
468:
690:
689:
685:
684:
683:
681:
680:
679:
645:
644:
631:
615:
614:
606:
598:
597:
593:
576:
564:
551:
550:
546:
531:
514:
513:
509:
500:
498:
489:
488:
484:
479:
472:
469:
457:
450:
443:
436:
429:
422:
415:
408:
401:
394:
379:
372:
365:
358:
351:
344:
321:
314:
307:
300:
293:
286:
279:
272:
265:
258:
251:
232:
220:colon principle
168:surreal numbers
148:
79:
51:
24:
17:
12:
11:
5:
688:
686:
678:
677:
672:
667:
662:
657:
647:
646:
643:
642:
637:
630:
629:External links
627:
626:
625:
613:
612:
591:
562:
544:
529:
507:
481:
480:
478:
475:
474:
473:
470:
463:
455:
448:
441:
434:
427:
420:
413:
406:
399:
392:
377:
370:
363:
356:
349:
342:
323:to the vertex
319:
312:
305:
298:
291:
284:
277:
270:
263:
256:
249:
231:
228:
186:and all other
147:
144:
134:
133:
125:
117:
104:partisan games
96:impartial game
78:
75:
50:
47:
15:
13:
10:
9:
6:
4:
3:
2:
687:
676:
673:
671:
668:
666:
663:
661:
658:
656:
653:
652:
650:
641:
638:
636:
633:
632:
628:
623:
622:
617:
616:
605:
604:"Game Theory"
602:(Fall 2000).
601:
595:
592:
587:
581:
573:
569:
565:
563:9781568811420
559:
555:
548:
545:
540:
536:
532:
530:0-521-57411-0
526:
522:
518:
511:
508:
497:
493:
486:
483:
476:
467:
462:
460:
458:
451:
444:
437:
430:
423:
416:
409:
402:
395:
388:
384:
380:
373:
366:
359:
352:
345:
338:
334:
330:
327:of the graph
326:
322:
315:
308:
301:
294:
287:
280:
273:
266:
259:
252:
245:
241:
237:
229:
227:
225:
221:
217:
211:
208:
204:
200:
196:
191:
189:
185:
181:
177:
173:
169:
165:
164:
159:
158:
153:
145:
143:
141:
140:
131:
130:
126:
123:
122:
118:
114:
113:
109:
108:
107:
105:
101:
97:
90:
89:
83:
76:
74:
71:
67:
62:
60:
55:
48:
46:
44:
43:line segments
40:
36:
28:
22:
619:
594:
553:
547:
520:
510:
499:. Retrieved
496:geometer.org
495:
490:Davis, Tom.
485:
453:
446:
439:
432:
425:
418:
411:
404:
397:
390:
386:
382:
375:
368:
361:
354:
347:
340:
336:
332:
328:
324:
317:
310:
303:
296:
289:
282:
275:
268:
261:
254:
247:
243:
239:
235:
233:
219:
212:
195:graph theory
192:
176:real numbers
161:
155:
149:
137:
135:
128:
127:
120:
119:
111:
110:
93:
86:
73:the ground.
63:
56:
52:
34:
33:
116:Hackenbush.
70:game theory
649:Categories
501:2023-02-12
477:References
35:Hackenbush
580:cite book
139:cold game
572:45102937
309: :
302:, where
295: :
274: :
199:vertices
180:ordinals
146:Analysis
77:Variants
66:finitely
49:Gameplay
539:1427953
224:nim sum
188:nimbers
570:
560:
537:
527:
246:. Let
607:(PDF)
242:, in
207:paths
203:edges
586:link
568:OCLC
558:ISBN
525:ISBN
438:and
410:and
396:and
346:and
335:and
281:and
253:and
201:and
184:star
160:and
452:or
424:or
216:Nim
651::
582:}}
578:{{
566:.
535:MR
533:.
494:.
374:+
360:+
337:G2
333:G1
288:=
267:=
190:.
178:,
609:.
588:)
574:.
541:.
504:.
456:2
454:H
449:1
447:H
442:2
440:H
435:1
433:H
428:2
426:H
421:1
419:H
414:2
412:H
407:1
405:H
400:2
398:H
393:1
391:H
387:G
383:G
378:2
376:G
371:1
369:G
364:2
362:G
357:1
355:G
350:2
348:G
343:1
341:G
329:G
325:x
320:i
318:H
313:i
311:H
306:x
304:G
299:2
297:H
292:x
290:G
285:2
283:G
278:1
276:H
271:x
269:G
264:1
262:G
257:2
255:H
250:1
248:H
244:G
240:x
236:G
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
