Jos W. H. M. Uiterwijk
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Interests
Jos W. H. M. Uiterwijk has a total of 87 co-authors. Here are the top co-authors by number of shared publications:
- Jaap van Den Herik
Leiden University, Netherlands
11 shared publications - Mark H. M. Winands
Maastricht University
9 shared publications H. Jaap van Den Herik
8 shared publicationsJ. van Reek
6 shared publications- J. van Reek
Margraten, The Netherlands
6 shared publications Jaap van Den Herik
Maastricht, The Netherlands
6 shared publications
Latest Publications
- 24 May 2023
- Published by Springer Nature
- p. 97-108
Solving Impartial SET Using Knowledge and Combinatorial Game Theory
- 24 May 2023
- Published by Springer Nature
- p. 97-108
Solving Impartial SET Using Knowledge and Combinatorial Game Theory
- 1 August 2022
- Published by Springer Nature
- p. 96-106
Solving Bicoloring-Graph Games on Rectangular Boards – Part 1: Partisan Col and Snort
- 1 August 2022
- Published by Springer Nature
- p. 96-106
Solving Bicoloring-Graph Games on Rectangular Boards – Part 1: Partisan Col and Snort
- 1 August 2022
- Published by Springer Nature
- p. 107-117
Solving Bicoloring-Graph Games on Rectangular Boards – Part 2: Impartial Col and Snort
- 1 August 2022
- Published by Springer Nature
- p. 107-117
Solving Bicoloring-Graph Games on Rectangular Boards – Part 2: Impartial Col and Snort
- 7 November 2019
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 41 (3) , 174-175
Special Issue on Combinatorial Games
- 7 November 2019
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 41 (3) , 174-175
Special Issue on Combinatorial Games
- 1 August 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-8
Solving Strong and Weak 4-in-a-Row
In this paper we first summarize knowledge about the standard (strong) version of the game 4-in-a-Row. It was previously shown that 4-in-a-Row is a draw on 4×n boards for n= 4–8, and on the 5×5 board as well. Further we know that the game is a (first-player) win on the 5×6 board. Finally it is stated that 4-in-a-Row is a win on a 4×30 board. It is not known if and where there is a transition from drawn games to won games on 4×n boards for n ranging from 9–29. Using our k-in-a-Row solver we then show that the 4×n boards for n= 9, 10, and 11 are wins. We provide the principal variations by our solver program for the 5×6 and 4×9 boards.Further we introduce a second version of the game, weak 4-ina-Row (also called Maker-Breaker (MB) 4-in-a-Row), where the second player wins if he is able to prevent the first player from winning, but does not win by obtaining a 4-in-a-Row sequence himself. This game benefits the first player, since he can safely ignore any "threats" by the second player. Our results show that for weak 4-in-a-Row the first player already wins on the 5×5 and 4×7 boards. We also provide the principal variations by our solver program for these boards.We then focus on the monotonicity property of winning positional games. It is widely believed that if a k-in-a-Row game is a win on some board, it will be a win on any larger board as well. This is denoted as a monotone win. As a consequence, if a k-in-a-Row game is a draw on some board, it will be a draw on any smaller board. For weak positional games the monotonicity property holds by definition. However, for the strong version of k-in-a-Row, the monotonicity property has never been formally proven. It is surely not true on arbitrary graphs, where enlarging the winning set might change a winning game into a draw. This phenomenon is known as the Extra Set Paradox. Still it is commonly believed that the monotonicity of winning does hold for rectangular boards. However, we show that even this is not true, at least not for arbitrary positions on a rectangular board. We demonstrate this with a counterexample.To deal with the problem of non-monotonicity we propose an algorithmic solution. Suppose that k-in-a-Row is a win on some m×n board (assuming arbitrarily that m≤n). To prove that this is a monotone win, we enlarge the board with a rim around the m×n board of width at most k−1. On this board the first player is only allowed to play on the inner board, whereas the second player may use the whole board. We show that if with these constraints the first player still wins, the game is also a win on any larger board. Using this method we have shown that the 5×6 board indeed is a monotone win. For the 4×9 board we had to make a small adaptation, namely that the first player is allowed to use the rim, but only to respond to useless direct threats by the opponent. Moreover, any such stone of the first player in the rim may not contribute to winning variations in any way. Using this we prove that also the win on the 4×9 board is monotone. With these results strong and weak 4-in-a-Row are completely solved.
- 1 August 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-8
Solving Strong and Weak 4-in-a-Row
In this paper we first summarize knowledge about the standard (strong) version of the game 4-in-a-Row. It was previously shown that 4-in-a-Row is a draw on 4×n boards for n= 4–8, and on the 5×5 board as well. Further we know that the game is a (first-player) win on the 5×6 board. Finally it is stated that 4-in-a-Row is a win on a 4×30 board. It is not known if and where there is a transition from drawn games to won games on 4×n boards for n ranging from 9–29. Using our k-in-a-Row solver we then show that the 4×n boards for n= 9, 10, and 11 are wins. We provide the principal variations by our solver program for the 5×6 and 4×9 boards.Further we introduce a second version of the game, weak 4-ina-Row (also called Maker-Breaker (MB) 4-in-a-Row), where the second player wins if he is able to prevent the first player from winning, but does not win by obtaining a 4-in-a-Row sequence himself. This game benefits the first player, since he can safely ignore any "threats" by the second player. Our results show that for weak 4-in-a-Row the first player already wins on the 5×5 and 4×7 boards. We also provide the principal variations by our solver program for these boards.We then focus on the monotonicity property of winning positional games. It is widely believed that if a k-in-a-Row game is a win on some board, it will be a win on any larger board as well. This is denoted as a monotone win. As a consequence, if a k-in-a-Row game is a draw on some board, it will be a draw on any smaller board. For weak positional games the monotonicity property holds by definition. However, for the strong version of k-in-a-Row, the monotonicity property has never been formally proven. It is surely not true on arbitrary graphs, where enlarging the winning set might change a winning game into a draw. This phenomenon is known as the Extra Set Paradox. Still it is commonly believed that the monotonicity of winning does hold for rectangular boards. However, we show that even this is not true, at least not for arbitrary positions on a rectangular board. We demonstrate this with a counterexample.To deal with the problem of non-monotonicity we propose an algorithmic solution. Suppose that k-in-a-Row is a win on some m×n board (assuming arbitrarily that m≤n). To prove that this is a monotone win, we enlarge the board with a rim around the m×n board of width at most k−1. On this board the first player is only allowed to play on the inner board, whereas the second player may use the whole board. We show that if with these constraints the first player still wins, the game is also a win on any larger board. Using this method we have shown that the 5×6 board indeed is a monotone win. For the 4×9 board we had to make a small adaptation, namely that the first player is allowed to use the rim, but only to respond to useless direct threats by the opponent. Moreover, any such stone of the first player in the rim may not contribute to winning variations in any way. Using this we prove that also the win on the 4×9 board is monotone. With these results strong and weak 4-in-a-Row are completely solved.
- 5 March 2019
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 40 (3) , 129-148
Set Matching with applications: An enhancement of the Hales–Jewett pairing strategy
When solving k -in-a-Row games, the Hales–Jewett pairing strategy [Trans. Amer. Math. Soc. 106 (1963 ), 222–229] is a well-known strategy to prove that specific positions are (at most) a draw for the first player. For non-overlapping possible winning
- 5 March 2019
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 40 (3) , 129-148
Set Matching with applications: An enhancement of the Hales–Jewett pairing strategy
When solving k -in-a-Row games, the Hales–Jewett pairing strategy [Trans. Amer. Math. Soc. 106 (1963 ), 222–229] is a well-known strategy to prove that specific positions are (at most) a draw for the first player. For non-overlapping possible winning
- 1 January 2018
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 40 (4) , 425-437
Construction and investigation of Cram endgame databases
In this paper we investigate the game of Cram, which is the impartial version of Domineering. We have built Cram endgame databases for all board sizes < 30 squares. We developed a program that fills the databases with their Combinatorial Game Theory (CGT) values. Since Cram is an impartial game, all CGT values for Cram positions are so-called nimbers, indicated by ∗ n . The nimber value of a position not only directly determines the game-theoretic value (first- or second-player win), but also provides an optimal playing strategy. When analyzing the resulting databases we observed the following facts. Firstly we confirmed that the CGT values of all investigated empty boards are in agreement with results published in the literature. Since the value of an empty board depends completely on the values of many partially filled positions in the database, this is a strong indication that our process of filling the database with CGT values is correct. Secondly, although the series of values for 2 × n boards is completely regular, namely a value ∗ 0 for n being even and ∗ 1 for n being odd, this was not proven formally so far. We were able to provide such a proof. We also investigated the databases for their contents. So far we encountered nimber values up to ∗ 11 among single-fragment Cram positions. It appears that for a ∗ n value to occur a board size with ≈ 3 n squares is needed, some more for very tall boards ( 1 × n ), some less for wider boards ( 4 × n ). So far no single-fragment Cram positions were encountered with nimber values ⩾ ∗ 12 , although we show a construction of larger multi-fragment positions with nimber values from ∗ 12 up to ∗ 15 . In a preliminary experiment we incorporated the CGT endgame databases constructed into a simple alpha-beta solver for the game. Results revealed a large improvement in solving power.
- 1 January 2018
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 40 (4) , 425-437
Construction and investigation of Cram endgame databases
In this paper we investigate the game of Cram, which is the impartial version of Domineering. We have built Cram endgame databases for all board sizes < 30 squares. We developed a program that fills the databases with their Combinatorial Game Theory (CGT) values. Since Cram is an impartial game, all CGT values for Cram positions are so-called nimbers, indicated by ∗ n . The nimber value of a position not only directly determines the game-theoretic value (first- or second-player win), but also provides an optimal playing strategy. When analyzing the resulting databases we observed the following facts. Firstly we confirmed that the CGT values of all investigated empty boards are in agreement with results published in the literature. Since the value of an empty board depends completely on the values of many partially filled positions in the database, this is a strong indication that our process of filling the database with CGT values is correct. Secondly, although the series of values for 2 × n boards is completely regular, namely a value ∗ 0 for n being even and ∗ 1 for n being odd, this was not proven formally so far. We were able to provide such a proof. We also investigated the databases for their contents. So far we encountered nimber values up to ∗ 11 among single-fragment Cram positions. It appears that for a ∗ n value to occur a board size with ≈ 3 n squares is needed, some more for very tall boards ( 1 × n ), some less for wider boards ( 4 × n ). So far no single-fragment Cram positions were encountered with nimber values ⩾ ∗ 12 , although we show a construction of larger multi-fragment positions with nimber values from ∗ 12 up to ∗ 15 . In a preliminary experiment we incorporated the CGT endgame databases constructed into a simple alpha-beta solver for the game. Results revealed a large improvement in solving power.
- 22 December 2017
- Published by Springer Nature
- p. 38-50
Set Matching: An Enhancement of the Hales-Jewett Pairing Strategy
- 22 December 2017
- Published by Springer Nature
- p. 38-50
Set Matching: An Enhancement of the Hales-Jewett Pairing Strategy
- 15 September 2017
- Published by Springer Nature
- p. 78-92
Combining Combinatorial Game Theory with an $\alpha $ - $\beta $ Solver for Clobber: Theory and Experiments- 15 September 2017
- Published by Springer Nature
- p. 78-92
Combining Combinatorial Game Theory with an $\alpha $ - $\beta $ Solver for Clobber: Theory and Experiments