Nim 挑战

• 下载源代码 - 251 Kb
• 在 Google Play 中查找该应用

引言

尼姆游戏是一种策略游戏，两名玩家轮流从不同的堆中移除物品。玩家可以移除任意数量的物品，只要它们都来自同一堆并且位置连续。移除所有堆中最后一件物品的玩家获胜。

我相信你们大多数人以前都玩过这个游戏，而且很多人可能也知道尼姆游戏绝不是一个靠运气取胜的游戏。相反，存在一种算法，如果应用得当，可以使两名玩家中的一名总是获胜。尼姆挑战是一款 Android 应用程序，它实现了这种“必胜策略”，并挑战玩家在不同情况和时间压力下应用它。

必胜策略

让我们从一个例子开始描述必胜策略。考虑一个由三堆物品组成的排列，一堆大小为 1，一堆大小为 2，一堆大小为 3。

这种排列可以表示如下

对于每一行，我们计算元素的数量。我们将该数字转换为其二进制表示。一个二进制数由 1 和 0 组成。在每一列中，我们计算 1 的数量。如果结果是奇数，则在 总和 的相应列中得到 1。如果结果是偶数，则得到 0。

如果 总和 全为零，则先出手的玩家输。另一方面，如果 总和 中甚至有一个 1，则先出手的玩家总是可以找到一个移动，将物品排列转换为总和为零的形式并获胜。

上述算法假设最后移除物品的玩家获胜。然而，游戏也经常以最后移除物品的玩家输的方式进行。这被称为“输者局”游戏。在“输者局”游戏中，可以应用相同的算法，但有一个例外，即只剩下大小为 1 的堆时。在这种情况下，玩家必须尝试留下奇数个大小为 1 的堆。

当你玩的时候，很难快速转换为二进制并计算总和。即使你这样做了，你仍然需要找到能够导致零和排列的移动，这也不容易。为了快速玩，你可以遵循一小组规则

• 1、2、3 的排列会输。
• 1、3、5 的排列会赢（将其转换为 1、2、3）。
• 每个数字出现偶数次的排列会输（例如 1,1,2,2 和 4,4）。你可以快速通过复制行来消除影响。
• 赢和输的排列组合会赢。

游戏模式

尼姆挑战提供三种不同的游戏模式。在经典模式中，使用原始的物品排列。玩家可以选择是否先手，但为了获胜，玩家必须先手。你可以尝试此模式进行练习并跟随电脑的移动。

在变体模式中，使用不同的物品排列。玩家选择是否先手。这是一个关键的决定，必须考虑具体的物品排列。如果玩家获胜，她可以继续玩另一局游戏。每次物品排列都会变得更复杂。在此模式中会记录分数。玩家必须尽快玩才能赢得更多分数。

在挑战模式中，你与时间赛跑。你只有有限的时间来找到最佳移动。如果时间用完，你就输了。在此模式中也会记录分数，更快的移动会赢得更多分数。

尼姆挑战还允许你创建自定义棋盘。你可以创建任意数量的自定义棋盘，并通过长按自定义棋盘列表中的棋盘来编辑它们。你可以使用此功能通过反复玩同一个棋盘来练习。

设置

游戏的以下方面可以配置

• 单次触摸：如果选中，每次移动无需确认即可立即执行。这更快，但没有机会纠正错误。
• 主题：选择棋盘的外观。
• 最后赢家：选择游戏是正常游戏（选中）还是输者局游戏（未选中）。在正常游戏中，移除最后一个元素的玩家获胜。在输者局游戏中，最后移除的玩家输。

以上设置影响所有游戏模式。

源代码

尼姆挑战的设计和实现遵循与Puzzles Solver相同的原则。这些原则在之前的文章中已详细描述。在此不再重复，我想简要提及我在实现尼姆挑战时遇到的一些挑战性问题。

绘制线条

游戏中所有的图形都使用 Canvas 绘图和简单的 View 对象。游戏的性质决定了不需要快速更新，因此不需要更高级的解决方案。然而，有一个细节需要特殊处理。为了从堆中选择物品，用户在屏幕上的两点之间划一条线

用户首先触摸屏幕选择起点，然后拖动手指选择终点。拖动时线条会动态更新。下面的代码片段展示了在 NimView 的 onTouchEvent 方法中如何处理动态更新。

switch(event.getAction())
{
case MotionEvent.ACTION_DOWN:
    // First touch - Set the starting point, reset the isAnimationDelayed flag, start the move
    isAnimationDelayed = false;
    if (moveState == MoveState.Move_Idle) {
        startPoint.set((int) event.getX(), (int) event.getY());
        endPoint.set((int) event.getX(), (int) event.getY());
        moveState = MoveState.Move_Started;
    }
case MotionEvent.ACTION_MOVE:
    // User drags his/her finger - set the ending point and update the line
    if (moveState == MoveState.Move_Started) {
        endPoint.set((int) event.getX(), (int) event.getY());
        // Only invalidate the view if more than 100ms (animationDelay) from the previous
        // update have passed
        if (!isAnimationDelayed) {
            isAnimationDelayed = true;
            animationDelayHandler.postDelayed(new Runnable() {
                @Override
                public void run() {
                    if (isAnimationDelayed) {
                        invalidate();
                        isAnimationDelayed = false;
                    }
                }

            }, animationDelay);
        }
    }
case MotionEvent.ACTION_UP:
    isAnimationDelayed = false;
    if (moveState == MoveState.Move_Started) {
        endPoint.set((int) event.getX(), (int) event.getY());
        moveState = MoveState.Move_Idle;
        
        // Find the objects selected by the user
    }
    

正如你所看到的，屏幕只在每 100 毫秒（或当用户抬起手指时）更新一次，而不是每次收到新的 ACTION_MOVE 事件时都更新。ACTION_MOVE 事件发送得太频繁，如果错误地响应每个事件，将会严重降低应用程序的性能。

时间计数器

为了计算游戏时间，我创建了一个简单的 TimeCounter 类。这个类使用 System.currentTimeMillis() 方法来测量时间，并且 NimGame（即游戏 Activity）和 NimView（即负责绘制游戏画布和处理用户输入的 View）都使用它的一个实例。

在 NimView 内部有一个 Handler，它每秒启动一个 Runnable 运行一次。

    // Constructor
    timerHandler = new Handler();
    
    // Start of time measurement
    timeCounter.start();
	timerHandler.postDelayed(timeRunnable, 1000);
    
    // Code to run once a second
	private Runnable timeRunnable = new Runnable() {
		@Override
		public void run() {
			if (gameState == GameState.User_Move || gameState == GameState.First_Player_Question) {
				// Re-draw the screen
                invalidate();
			}
			timerHandler.postDelayed(timeRunnable, 1000);
		}
	};        
    

在 onDraw 方法中，更新后的时间会呈现在屏幕上。检查时间是否过期也发生在那里。这给用户额外的毫秒时间来响应。

从所有这些来看，似乎 TimeCounter 只需要由 NimView 使用，并且没有理由与 NimGame 共享。NimGame 需要访问 TimeCounter 的原因与应用程序的生命周期处理有关。NimGame 托管 onPause 和 onResume 方法，其中需要执行一些重要的时间相关操作。当然，当调用 onPause 方法时，计时器需要暂停。例如，当游戏过程中手机响起时，就会发生这种情况。我们希望用户接听电话，然后返回游戏，而时间没有前进。因此，一个解决方案是在调用 onResume 方法时恢复计时器。然而，这并不总是那么简单。在某些设备上，当用户关闭屏幕时，可能不会调用 onResume 方法。在这种情况下，应用程序将处于锁定屏幕后面。解锁屏幕后，不会调用 onResume。可以注册一个广播接收器来监视事件。或者利用 public void onWindowFocusChanged (boolean hasFocus) 方法。这些都是复杂的解决方案，并且可能无法在所有设备上以相同的方式工作。然而，我不认为其中任何一个实际上是必需的。有一种替代方案既更简单又提供更好的用户体验。为了处理这些情况，我们遵循这种模式

• 当应用程序暂停或失去前台焦点时，暂停计时器。将屏幕变灰以指示游戏处于暂停模式。
• 要求用户操作以恢复计时器。每当用户返回到用户时，他/她会看到一个变灰的屏幕，并且必须触摸屏幕上的任何位置才能继续。

这种逻辑易于实现，在所有设备上以及在应用程序进入后台的所有情况下都能很好地工作，最重要的是为用户提供了更好的体验。

    @Override
    public void onPause() {
        super.onPause();

        if (!gameFinished) {
            // Pause the timer
            timeCounter.pause();
            // Pause the view - the screen will be grayed out and a "Pause" message will appear
            nimView.setPaused(true);
        }
    }

    @Override
    public void onResume() {
        super.onResume();

        // Invalidate the view for the gray-out screen to appear - wait for user input to continue
        nimView.invalidate();
    }        
    

历史

• 文章第一版