All Questions
Tagged with gt.game-theory board-games
6 questions
11
votes
0
answers
206
views
Is 4-in-a-row PSPACE-complete?
This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
- 682
5
votes
0
answers
823
views
Games on Turing machines that are AH-hard
I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-...
- 1,046
11
votes
3
answers
954
views
Implementation of surreal numbers for games
There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
- 9,018
8
votes
4
answers
287
views
Examples of Computer-Found Optimal Strategies in Games
I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.
- 181
-5
votes
1
answer
2k
views
Developing A Perfect Tic-Tac-Toe Player - AI [closed]
I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
- 101
2
votes
3
answers
1k
views
What games best represent well-known computer science problems?
I heard that Clue is a board game that is related to the NP-complete traveling salesman problem. What are other games that relate to important computational problems?
- 161