162:). This is because an extra stone given to either player in any position can only improve that player's chances. The strategy stealing argument assumes that the second player has a winning strategy and demonstrates a winning strategy for the first player. The first player makes an arbitrary move, to begin with. After that, the player pretends that they are the second player and adopts the second player's winning strategy. They can do this as long as the strategy doesn't call for placing a stone on the 'arbitrary' square that is already occupied. If this happens, though, they can again play an arbitrary move and continue as before with the second player's winning strategy. Since an extra stone cannot hurt them, this is a winning strategy for the first player. The
1000:
446:= 9 and the board is infinite, the second player can draw via a "pairing strategy". A draw on an infinite board means that the game will go on forever with perfect play. A pairing strategy involves dividing all the squares of the board into pairs in such a way that by always playing on the pair of the first player's square, the second player is ensured that the first player cannot get
22:
450:
in a line. A pairing strategy on an infinite board can be applied to any finite board as well – if the strategy calls for making a move outside the board, then the second player makes an arbitrary move inside the
169:
This argument tells nothing about whether a particular game is a draw or a win for the first player. Also, it does not actually give a strategy for the first player.
457:≥ 8 is a draw on an infinite board. It is not clear if this strategy applies to any finite board sizes. It is not known if the second player can force a draw when
794:
877:
Elwyn R. Berlekamp, John Horton Conway, Richard K. Guy. "Winning ways for your mathematical plays, Volume 3", A K Peters (2003)
907:
250:
Note that proofs of draws using pairing strategies also prove a draw for the weak version and thus for all smaller versions.
1043:
258:
The following statements refer to the first player in the weak game, assuming that both players use an optimal strategy.
761:
617:
Computer search by Wei-Yuan Hsu and Chu-Ling Ko has shown that both (7,7,5) and (8,8,5) are draws, which means that (
1162:
835:, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence.
1172:
720:
that the game is a draw also when the number of cells is at least twice the number of lines, which happens
979:
659:
It is possible to consider variants played on a multidimensional board instead of a bidimensional board.
1053:
900:
166:
implies that the original assumption is false, and the second player cannot have a winning strategy.
143:
1048:
1167:
846:
163:
1106:
1063:
158:-game can there be a strategy that assures that the second player will win (a second-player
1079:
984:
924:
893:
702:
683:
8:
1100:
1038:
969:
766:
832:
139:
1131:
989:
159:
64:
stones of their own color in a row, horizontally, vertically, or diagonally. Thus,
959:
954:
634:
999:
932:
721:
654:
193:-in-a-row by the second player does not end the game with a second player win.
1156:
637:
has shown that (15,15,5) is a win, even with one of the restrictive rules of
49:
1121:
851:
746:
123:
1136:
1116:
1058:
947:
916:
508:
127:
119:
115:
65:
483:
is a draw, also by a pairing strategy in the dimension not smaller than
1111:
1084:
789:
717:
45:
671:
1126:
751:
845:
Hsu, Wei-Yuan; Ko, Chu-Ling; Hsueh, Chu-Hsuan; Wu, I-Chen (2018).
1141:
1094:
1030:
942:
771:
21:
937:
756:
638:
69:
885:
974:
964:
784:
779:
172:
678:, Hales and Jewett proved that the game is a draw if
504:= 2 are trivial wins, except for (1,1,2) and (2,1,2)
487:(or trivially impossible to win if both are smaller)
52:take turns in placing a stone of their color on an
60:board, the winner being the player who first gets
828:
826:
1154:
644:(9,6,6) and (7,7,6) are both draws via pairings.
812:
810:
823:
816:J. W. H. M. Uiterwijk and H. J van der Herik,
901:
570:≤ 5, and (6,5,4) is a win, which means that (
133:
844:
820:, Information Sciences 122 (1) (2000) 43-58.
807:
648:
908:
894:
602:≥ 30 (Lustenberger, 1967) and a draw for
173:Applying results to different board sizes
20:
1155:
889:
554:(5,5,4) is a draw, which means that (
847:"Solving 7,7,5-game and 8,8,5-game"
491:
122:value, the result of the game with
25:Example of a completed 11,10,5-game
18:Abstract board game for two players
13:
253:
235:) is a win, then any larger weak (
220:will also result in a drawn game.
14:
1184:
610:,4,4) is a win or a draw for 9 ≤
68:is the 3,3,3-game and free-style
1044:Harary's generalized tic-tac-toe
998:
666:-in-a-row where the board is an
118:interest. One seeks to find the
915:
818:The advantage of the initiative
461:is 6 or 7 on an infinite board.
223:Conversely, if weak or normal (
871:
838:
762:Harary's generalized tictactoe
1:
801:
208:) is a draw, then decreasing
177:A useful notion is a "weak (
7:
739:
674:with all edges with length
10:
1189:
1054:Strategy-stealing argument
652:
134:Strategy stealing argument
1072:
1007:
996:
923:
349:is a draw. Likewise, if (
144:combinatorial game theory
649:Multidimensional variant
633:≤ 8. Computer search by
72:is the 15,15,5-game. An
1163:Abstract strategy games
606:≤ 8. It is unknown if (
507:(3,3,3) is a draw (see
84:-game is also called a
1173:Partially solved games
26:
1064:Paper-and-pencil game
114:-games are mainly of
24:
1049:Hales–Jewett theorem
985:Ultimate tic-tac-toe
442:≥ 9 is a draw: when
970:Quantum tic-tac-toe
598:,4,4) is a win for
283:) is a draw, then (
126:. This is known as
1107:Three men's morris
833:Jaap van den Herik
625:,5) is a draw for
562:,4) is a draw for
370:) is a win, then (
27:
1150:
1149:
1080:Nine men's morris
578:,4) is a win for
519:,3) is a draw if
262:If a particular (
146:shows that in no
140:strategy stealing
1180:
1039:Kaplansky's game
1008:Related concepts
1002:
990:Wild tic-tac-toe
910:
903:
896:
887:
886:
878:
875:
869:
868:
866:
864:
842:
836:
830:
821:
814:
767:Kaplansky's game
662:For the case of
535:,3) is a win if
492:Specific results
312:is a draw, and (
216:, or increasing
160:winning strategy
1188:
1187:
1183:
1182:
1181:
1179:
1178:
1177:
1153:
1152:
1151:
1146:
1068:
1003:
994:
960:Order and Chaos
955:Number Scrabble
919:
914:
883:
881:
876:
872:
862:
860:
843:
839:
831:
824:
815:
808:
804:
799:
742:
657:
651:
635:L. Victor Allis
494:
467:≥ 3 and either
435:
424:
413:
399:is a win, and (
398:
383:
376:
369:
362:
355:
348:
337:
326:
311:
296:
289:
282:
275:
268:
256:
254:General results
189:) game", where
175:
136:
44:is an abstract
19:
12:
11:
5:
1186:
1176:
1175:
1170:
1168:In-a-row games
1165:
1148:
1147:
1145:
1144:
1139:
1134:
1129:
1124:
1119:
1114:
1109:
1104:
1097:
1092:
1091:
1090:
1082:
1076:
1074:
1070:
1069:
1067:
1066:
1061:
1056:
1051:
1046:
1041:
1036:
1028:
1011:
1009:
1005:
1004:
997:
995:
993:
992:
987:
982:
977:
972:
967:
962:
957:
952:
951:
950:
940:
935:
933:3D tic-tac-toe
929:
927:
921:
920:
913:
912:
905:
898:
890:
880:
879:
870:
837:
822:
805:
803:
800:
798:
797:
792:
787:
782:
777:
769:
764:
759:
754:
749:
743:
741:
738:
737:
736:
722:if and only if
714:
713:
695:
694:
655:3D tic-tac-toe
650:
647:
646:
645:
642:
615:
552:
505:
493:
490:
489:
488:
462:
452:
437:
433:
422:
411:
396:
381:
374:
367:
360:
353:
346:
335:
324:
309:
294:
287:
280:
273:
266:
255:
252:
174:
171:
142:argument from
135:
132:
120:game-theoretic
17:
9:
6:
4:
3:
2:
1185:
1174:
1171:
1169:
1166:
1164:
1161:
1160:
1158:
1143:
1140:
1138:
1135:
1133:
1130:
1128:
1125:
1123:
1120:
1118:
1115:
1113:
1110:
1108:
1105:
1103:
1102:
1098:
1096:
1093:
1088:
1087:
1086:
1083:
1081:
1078:
1077:
1075:
1073:Similar games
1071:
1065:
1062:
1060:
1057:
1055:
1052:
1050:
1047:
1045:
1042:
1040:
1037:
1035:
1033:
1029:
1027:
1025:
1021:
1017:
1013:
1012:
1010:
1006:
1001:
991:
988:
986:
983:
981:
978:
976:
973:
971:
968:
966:
963:
961:
958:
956:
953:
949:
946:
945:
944:
941:
939:
936:
934:
931:
930:
928:
926:
922:
918:
911:
906:
904:
899:
897:
892:
891:
888:
884:
874:
858:
854:
853:
848:
841:
834:
829:
827:
819:
813:
811:
806:
796:
793:
791:
788:
786:
783:
781:
778:
776:
774:
770:
768:
765:
763:
760:
758:
755:
753:
750:
748:
745:
744:
734:
730:
726:
725:
724:
723:
719:
711:
708:
707:
706:
704:
700:
692:
689:
688:
687:
685:
681:
677:
673:
670:-dimensional
669:
665:
660:
656:
643:
640:
636:
632:
628:
624:
620:
616:
613:
609:
605:
601:
597:
593:
589:
585:
581:
577:
573:
569:
565:
561:
557:
553:
550:
546:
542:
538:
534:
530:
526:
522:
518:
514:
510:
506:
503:
499:
496:
495:
486:
482:
478:
474:
470:
466:
463:
460:
456:
453:
449:
445:
441:
438:
432:
428:
421:
417:
410:
406:
402:
395:
391:
387:
380:
373:
366:
359:
352:
345:
341:
334:
330:
323:
319:
315:
308:
304:
300:
293:
286:
279:
272:
265:
261:
260:
259:
251:
248:
246:
242:
238:
234:
230:
226:
221:
219:
215:
211:
207:
203:
199:
194:
192:
188:
184:
180:
170:
167:
165:
164:contradiction
161:
157:
153:
149:
145:
141:
131:
129:
125:
121:
117:
113:
109:
105:
100:
98:
94:
90:
88:
83:
79:
75:
71:
67:
63:
59:
55:
51:
48:in which two
47:
43:
41:
37:
33:
23:
16:
1122:Connect Four
1099:
1089:Tic-Stac-Toe
1031:
1023:
1019:
1015:
1014:
882:
873:
861:. Retrieved
856:
852:ICGA Journal
850:
840:
817:
772:
747:Connect Four
732:
728:
715:
709:
698:
696:
690:
679:
675:
667:
663:
661:
658:
630:
626:
622:
618:
611:
607:
603:
599:
595:
591:
587:
583:
579:
575:
571:
567:
563:
559:
555:
548:
544:
540:
536:
532:
528:
524:
520:
516:
512:
501:
497:
484:
480:
476:
472:
468:
464:
458:
454:
447:
443:
439:
430:
426:
419:
415:
408:
404:
400:
393:
389:
385:
378:
371:
364:
357:
350:
343:
339:
332:
328:
321:
317:
313:
306:
302:
298:
291:
284:
277:
270:
263:
257:
249:
247:) is a win.
244:
240:
236:
232:
228:
224:
222:
217:
213:
209:
205:
201:
197:
195:
190:
186:
182:
178:
176:
168:
155:
151:
147:
137:
124:perfect play
116:mathematical
111:
107:
103:
101:
96:
92:
86:
85:
81:
77:
73:
61:
57:
53:
39:
35:
31:
30:
28:
15:
1137:Toss Across
1059:Futile game
948:Treblecross
917:Tic-tac-toe
509:Tic-tac-toe
138:A standard
91:game on an
66:tic-tac-toe
1157:Categories
1112:Nine Holes
1085:Score Four
863:6 November
802:References
790:Score Four
718:conjecture
653:See also:
523:< 3 or
130:the game.
46:board game
672:hypercube
527:< 3. (
436:is a win.
196:If weak (
89:-in-a-row
1127:Connect6
925:Variants
752:Connect6
740:See also
712:≥ 2 − 2.
629:≤ 8 and
590:≥ 5 and
582:≥ 6 and
566:≤ 5 and
547:≥ 4 and
539:≥ 3 and
511:), and (
500:= 1 and
1142:Pentago
1095:Gobblet
943:Notakto
795:Eternas
693:≥ 3 − 1
586:≥ 5 or
543:≥ 4 or
414:) with
388:) with
327:) with
301:) with
128:solving
99:board.
50:players
1101:Quarto
938:Gomoku
757:Gomoku
697:or if
639:Gomoku
594:≥ 6. (
451:board.
70:gomoku
1026:-game
975:Renju
965:Pente
785:Qubic
780:Pente
735:+ 2).
716:They
705:and
686:and
614:≤ 29.
479:>
471:>
42:-game
1117:Achi
1034:game
865:2019
775:game
703:even
551:≥ 3.
425:and
338:and
102:The
95:-by-
56:-by-
1132:OXO
980:SOS
859:(3)
731:≥ (
701:is
684:odd
682:is
475:or
212:or
29:An
1159::
857:40
855:.
849:.
825:^
809:^
727:2
429:≥
418:≥
407:,
403:,
392:≤
384:,
377:,
363:,
356:,
342:≤
331:≤
320:,
316:,
305:≥
297:,
290:,
276:,
269:,
1032:n
1024:k
1022:,
1020:n
1018:,
1016:m
909:e
902:t
895:v
867:.
773:n
733:k
729:k
710:k
699:k
691:k
680:k
676:k
668:n
664:k
641:.
631:n
627:m
623:n
621:,
619:m
612:m
608:m
604:m
600:m
596:m
592:n
588:m
584:n
580:m
576:n
574:,
572:m
568:n
564:m
560:n
558:,
556:m
549:n
545:m
541:n
537:m
533:n
531:,
529:m
525:n
521:m
517:n
515:,
513:m
502:k
498:k
485:k
481:n
477:k
473:m
469:k
465:k
459:k
455:k
448:k
444:k
440:k
434:0
431:n
427:n
423:0
420:m
416:m
412:0
409:k
405:n
401:m
397:0
394:k
390:k
386:k
382:0
379:n
375:0
372:m
368:0
365:k
361:0
358:n
354:0
351:m
347:0
344:n
340:n
336:0
333:m
329:m
325:0
322:k
318:n
314:m
310:0
307:k
303:k
299:k
295:0
292:n
288:0
285:m
281:0
278:k
274:0
271:n
267:0
264:m
245:k
243:,
241:n
239:,
237:m
233:k
231:,
229:n
227:,
225:m
218:k
214:n
210:m
206:k
204:,
202:n
200:,
198:m
191:k
187:k
185:,
183:n
181:,
179:m
156:k
154:,
152:n
150:,
148:m
112:k
110:,
108:n
106:,
104:m
97:n
93:m
87:k
82:k
80:,
78:n
76:,
74:m
62:k
58:n
54:m
40:k
38:,
36:n
34:,
32:m
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
