-1
votes
1answer
64 views

Chess Game with N knights [on hold]

Given an infinite chess board containing N knights. The bottom left corner of the board is labelled as (0,0). Two geeks decide to play the following game on the board : In one turn, a player may move ...
0
votes
1answer
60 views

Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
-1
votes
1answer
180 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
2answers
41 views

Do most nonograms not require backtracking?

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, ...
1
vote
1answer
33 views

An algorithm to rate players in team?

I would like to design an algorithm to rate players in a team sport. One team of N players plays a match against another team of N players. The individual players will possibly change, from match to ...
0
votes
2answers
384 views

Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
4
votes
1answer
67 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
1
vote
1answer
67 views

Game Of Strings

There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a ...
2
votes
1answer
151 views

Largest white rectangle on board

Given a string rectangular board which is divided into unit cells. Each cell is initially painted black or white. The character board[i][j] represents the cell with coordinates (i, j). Each of those ...
2
votes
1answer
116 views

Play with pairs of numbers

Two players are playing a game. The game is played on a sequence of positive integer pairs. The players make their moves alternatively. During his move the player chooses a pair and decreases the ...
1
vote
1answer
55 views

Game of chocolates

Two players A and B play a game alternatively and A starts the game. Their are 2 boxes of chocolates and we are Given the number of chocolates in both the boxes, let them be c1 and c2, the player ...
1
vote
2answers
59 views

Maze Connectivity

Given a grid maze which is an n × m rectangle maze where each cell is either empty, or is a wall. One can go from one cell to another only if both cells are empty and have a common side. Initially we ...
0
votes
0answers
51 views

Rectangle over rectangle

Given N rectangles cut out of paper. The rectangles are labeled 0 through N-1.I am having given int[]s X and Y with N elements each. For each i, the sides of rectangle i have lengths X[i] and Y[i]. ...
0
votes
0answers
25 views

what calculation/algorithm should I consider for finding the winner(s) of a series of games

first of all I'm not in any way a mathematician, so be kind ;) Our current routine: The game is a card game. At the end of each round cards still in your hand are summed up and make your points. The ...
1
vote
0answers
123 views

Make the maximum sum in a interval.

Two players $A$ and $B$ are playing a game with array $A$ of $N$ elements in which each player chooses an array interval with maximum sum. The other simultaneously chooses another interval in the same ...
1
vote
1answer
122 views

K piles stone game

Their are k piles with total n stones in some order where each pile can have stones greater or equal to zero.Two player A and B plays a game in which player A cant see the configuration of piles but ...
1
vote
1answer
40 views

Flipping the Grid

Suppose a grid of size N * M is having only 1 and 0. The rows are numbered from 1 to N, and the columns are numbered from 1 to M. Following steps can be called as a single move. Select two integers ...
0
votes
1answer
85 views

Partisan/Partial Game Theory

There are enough resources available on the internet regarding "impartial" game theory. But I cannot seem to find much information regarding "partial" game theory. Can someone name some such resources ...
2
votes
1answer
152 views

Placing K knights in an nxn board such that no two attack each other

This is a problem from spoj A and B are playing a very interesting variant of the ancient Indian game 'shatranj(also known as chess)' on a 'maidaan'(chessboard) n×n in size. They take turns ...
2
votes
1answer
526 views

Finding Pareto optimal solution set in $O(n \log n)$ time

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...
3
votes
1answer
84 views

Effecient way to find optimal solution in a 2 player game

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 ...
0
votes
1answer
62 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
1
vote
0answers
56 views

Any known strategies for toads and frogs?

Are there any heuristic strategic for playing Toads and Frogs known? I reckon the optimal playthrough may be hard to achieve due to the game being NP-hard but at least something that regularly ...
1
vote
4answers
167 views

How to solve real-time games?

In game theory, we can solve a game by calculating its game tree as backward induction. This method seems to work for turn-based games, but how about real-time games? Are they have game trees? It ...
1
vote
2answers
129 views

Some Questions About Chess

I have to questions about the chess game: please help me to understand it. 1- How can a computer program know if this move or that move is better? It calculates all possbile continuation and examine? ...
3
votes
0answers
339 views

Simple game with coins - strategy

Let's play a game: There are $n$ stacks of coins in a row. $i$-th stack consists of $d_i$ coins. Two players: $\text{Player1},\text{Player2}$ make moves alternately. Player in his turn can only take ...
32
votes
1answer
1k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
2
votes
1answer
72 views

game strategy question

Let's say there are doors each with a lock on the integral points ($0$, $\pm1$, $\pm2$, $\cdots$) of the line. You are given a key which can only open a single lock, but you are not told what lock the ...
1
vote
1answer
775 views

Finding Nash equilibria using Support Enumeration

Chapter 3 of the Book "Algorithmic Game Theory" introduces an algorithm (page 8 of that PDF) to find mixed Nash equilibria for a bimatrix game $(A, B)$, which I struggle to understand. ($M$ and $N$ ...
2
votes
2answers
211 views

Mixed strategy nash equilibria in from $2\times N$ bimatrix form

I'm looking for a way of finding (manually!) mixed strategy Nash equilibria in a $2\times N$ game. Calling player 1 the player with two strategies and player 2 the one with $N$ strategies, I've ...